Originally posted by user Juvian:

This can be solved in O(n) either with Manchester or palindromic tree : adilet.org/blog/25-09-14

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.

Originally posted by user Juvian:

This can be solved in O(n) either with Manacher's algorithm or palindromic tree : adilet.org/blog/25-09-14

Both Manacher 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.