Finding the longest palindromic substring in linear time.
Finding the longest palindromic substring in a given string is a classic problem. A naive O(n^3) solution would check every substring for being a palindrome. A better, O(n^2) dynamic programming or 'expand from center' approach is more common. However, Manacher's algorithm provides a remarkably clever O(n) solution. The main challenge in the 'expand from center' approach is handling both odd-length palindromes (like 'racecar', centered at 'e') and even-length palindromes (like 'aabbaa', centered between the two 'b's). Manacher's algorithm elegantly solves this by transforming the input string. It inserts a special character (like '#') between every character of the original string (and at the ends). For example, 'aba' becomes '#a#b#a#'. Now, every palindrome in the transformed string has an odd length and a single, well-defined center. The algorithm then proceeds like an optimized 'expand from center'. It maintains a 'center' `C` and 'right boundary' `R` of the palindrome found so far that extends the furthest to the right. For each new position `i`, it uses the information from its mirror position `i'` (with respect to `C`) to intelligently initialize the palindrome length at `i`, avoiding redundant comparisons that are contained within the already-discovered palindrome `[C, R]`. This optimization is what brings the complexity down to linear time.