1. One-Liner
Manacher’s algorithm finds the longest palindromic substring (and all odd/even radii) in O(n) by tracking palindrome mirrors around centers and reusing known symmetry.
2. The Problem It Solves
Given S, find the maximum-length substring that reads the same forwards and backwards. Naive center expansion is O(n²); Manacher achieves linear total work with clever reuse.
3. The Core Idea
Insert sentinels (e.g. # between characters) to handle even and odd lengths uniformly. For each center, maintain how far the palindrome reaches; inside a bigger palindrome, mirror a smaller palindrome’s radius unless it hits the boundary.
4. How It Works (Table)
| Step | What Happens |
|---|---|
| 1 | Transform S → T with separators. |
| 2 | Arrays P[i] = radius of palindrome at i in T. |
| 3 | Track C (center) and R (right edge of palindrome covering i). |
| 4 | For each i, set initial P[i] from mirror; expand while chars match; update C,R. |
5. Dry Run Example
"aba" → transformed string; centers at middle letters yield radius counts mapping back to length 3 for "aba".
6. Key Properties
| Property | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
| Output | Longest length or all maximal palindromes |
7. Where It Is Used
| Domain | Use |
|---|---|
| DNA / RNA | Inverted repeats |
| NLP | Palindrome features, symmetry cues |
| Interviews | Canonical “linear palindrome” solution |
8. Interview Tips
Explain sentinel trick and mirror formula P[i] = min(R-i, P[mirror]). Fallback: expand centers O(n²) if time is tight.
9. Comparison with Other Algorithms
| Approach | Time |
|---|---|
| Brute | O(n³) |
| Center expand | O(n²) |
| Manacher | O(n) |
| Hash + binary search | O(n log n) |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Implementation Example (PYTHON)
def longest_palindrome(s):
if not s:
return ''
t = '#'.join('^{}