Four Ways to Find the Longest Palindrome, from O(n³) to O(n)
The center-expansion method is the practical takeaway for any developer who might face a string-manipulation interview; it is fast enough, uses no extra memory, and is short enough to write on a whiteboard. Manacher's, while rarely required, is the canonical example of how symmetry can drive an algorithm to its theoretical limit.
A brute-force enumeration of all substrings runs in O(n³) and times out on LeetCode. Dynamic programming cuts the time to O(n²) by caching whether smaller substrings are palindromic, at the cost of O(n²) memory. Center expansion achieves the same O(n²) time with O(1) space by growing outward from each possible palindrome center — the approach most recommended for interviews. Manacher's Algorithm unifies odd- and even-length palindromes with a preprocessing step and exploits symmetry to reach O(n) time, though the code is harder to produce under pressure. The progression from brute force to Manacher's mirrors a classic optimization arc: identify redundant work, cache intermediate results, then exploit structural properties to eliminate the cache.
The four-solution progression is a miniature curriculum in algorithm optimization: identify repeated work, cache it, then find a structural insight that makes the cache unnecessary.
Center expansion is often superior to dynamic programming for palindrome problems because the symmetry property lets you discard the DP table entirely without losing time efficiency.
Manacher's Algorithm is less about raw speed in practice — O(n²) is fine for typical constraint sizes — and more about proving that a linear-time solution exists for a problem that initially looks quadratic.