Originally posted by [user Juvian][1]:

This can be solved in O(n) either with Manchester or palindromic tree : [adilet.org/blog/25-09-14][2]
 	 	
Both manchester and palindromic tree are a bit harder to implement and definitely not easy to understand, so as long as performance is not needed its good to avoid them. 


 [1]: https://codereview.stackexchange.com/users/84671/juvian
 [2]: http://adilet.org/blog/25-09-14