Manacher's Algorithm
hardTime: O(n)Space: O(n)
Recognize the pattern
find all palindromes centered at each position in O(n)mirror property within known palindromes
Brute force idea
Expand around each center — O(n²).
Better approach
Manacher's: use known palindrome radii to skip redundant expansion. Maintain rightmost boundary and center. O(n).
Key invariant
If position i is within a known palindrome, the mirror's radius provides a starting point. Only expand beyond the known boundary.
Watch out for
Not handling boundary cases when the mirror's palindrome extends beyond the rightmost boundary.