Algorithms / Palindrome Manacher Lite
Least You Need to Know: Palindrome Centers, Symmetry, and Manacher-Lite Intuition
Palindrome reasoning starts from centers and symmetry. Manacher's algorithm pushes that idea further by reusing information from the current rightmost palindrome to compute all palindrome radii in linear time.
The least you need to know
- Every palindrome has a center: one character or a gap between two characters.
- Center expansion is the simple baseline for palindrome detection.
- Manacher reuses mirror information inside the current rightmost palindrome.
- Odd-length and even-length palindromes need compatible handling.
- Symmetry is the core invariant, not magic indexing.
Key notation
center
middle point around which a palindrome is symmetric
radius
how far a palindrome extends from its center
mirror
reflected center inside the current known palindrome window
Tiny worked example
- In `racecar`, the center is `e` and expansion matches characters symmetrically outward.
- If you already know a long palindrome window, a mirrored center inside that window inherits a lower bound on its radius.
- Manacher uses that reuse to skip repeated comparisons.
- The same center idea handles both odd and even palindromes with the right representation.
Common mistakes
- Students often forget even-length palindromes have centers between characters.
- Mirror reuse gives a starting radius, not always the full final radius.
- Manacher is about palindrome radii, not lexicographic order.
How to recognize this kind of problem
- The problem asks for many palindrome lengths or the longest palindromic substring.
- Center expansion is obvious but quadratic in the worst case.
- Symmetry around centers is the essential reasoning tool.
Next recommended lesson
Continue through this topic with Least You Need to Know: Partitioning Invariants and Dutch-Flag Regions.
Least You Need to Know: Partitioning Invariants and Dutch-Flag RegionsRelated lessons
Keep going with nearby lessons in the same topic.