The Longest Palindrome, Fast — Solution & Editorial

Back to the Problem

Manacher gives every center's maximal radius in O(n); odd centers yield length 2r−1, even centers 2r.

Complexity: O(|S|)