Manacher's Algorithm
hardTime: O(n)Space: O(n)
Signals to notice
find all palindromes centered at each position in O(n)mirror property within known palindromes
Brute force first
Expand around each center — O(n²).
The key insight
Manacher's: use known palindrome radii to skip redundant expansion. Maintain rightmost boundary and center. O(n).
What must stay true
If position i is within a known palindrome, the mirror's radius provides a starting point. Only expand beyond the known boundary.
Easy way to go wrong
Not handling boundary cases when the mirror's palindrome extends beyond the rightmost boundary.