A smarter solution tries every position in the original string as the center of a palindrome and extends to the left and to the right as long as the corresponding characters match. This solution takes O(n^2^) time.

There's a O(n log n) solution that involves rolling hash. Given X we can test if there is any substring S' of S of length 2X such that H(S') == H(reverse(S')). The identity means that S contains a palindromic sequence of length at least 2X. What is left is to find out the maximum X for which we can find a S' such that the equality holds. We can use binary search to do that efficiently. The overall complexity is O(n log n).

There's a O(n log n) solution that involves rolling hash. Given X we can test if there is any substring S' of S of length 2X such that H(S') == H(reverse(S')). The identity means that S contains a palindromic sequence of length at least 2X. What is left is to find out the maximum such X. We can use binary search to do that efficiently. The overall complexity is O(n log n).

h2. Substrings of variable length