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.