Manacher's Algorithm Explained

Manacher’s algorithm finds the longest palindromic substring of a string in linear time, O(n), by reusing information from palindromes it has already found instead of checking every possible substring from scratch. The naive approach — testing every center and expanding outward — takes O(n²) in the worst case; Manacher’s algorithm gets the same answer in a single pass.

The problem it solves

A palindrome reads the same forwards and backwards, like racecar or abba. Given a string, the longest palindromic substring problem asks for the longest contiguous slice that is itself a palindrome. This shows up often enough in string-processing interview questions and real text-processing tasks (like finding repeated symmetric patterns in DNA sequences or text) that it’s worth knowing a technique that doesn’t degrade to quadratic time on long inputs.

The brute-force approach picks every possible center point (a palindrome is either centered on a character, for odd length, or between two characters, for even length) and expands outward while the characters match. That’s O(n) centers times O(n) expansion in the worst case, giving O(n²) overall — fine for short strings, slow for long ones.

Handling odd and even length uniformly

Before the core trick, Manacher’s algorithm removes an annoying special case: palindromes can have an odd number of characters (racecar, centered on e) or an even number (abba, centered between the two bs). Handling both cases with different code is error-prone, so the standard technique transforms the string by inserting a separator character (commonly #) between every character and at both ends:

abba  →  #a#b#b#a#

Every palindrome in the transformed string is now odd-length, centered on a single character, regardless of whether the original palindrome was odd or even. This transformation is O(n) and lets the rest of the algorithm use one uniform code path.

The key insight: reusing symmetry

The naive algorithm treats each center independently, throwing away everything it learned at the previous center before moving to the next. Manacher’s algorithm keeps a running record of the rightmost palindrome found so far — its center C and the position R where it ends — and uses that record to skip redundant work at every subsequent center.

Here’s why that helps: if the current center i falls inside the current rightmost palindrome (i.e., i < R), then i has a mirror position i' reflected across C. Because the region around C is a palindrome, whatever palindrome radius was found at i' gives a lower bound, for free, on the palindrome radius at i — you don’t need to re-expand character by character to rediscover it. The algorithm only needs to expand outward from that lower bound, and only as far as the boundary R allows before checking beyond it.

This is the same kind of amortized reasoning that shows up in other linear-time string algorithms — KMP reuses partial-match information instead of restarting comparisons, and the Z-algorithm reuses previously computed Z-values the same way Manacher’s algorithm reuses palindrome radii. In all three cases, the total number of character comparisons across the whole pass is bounded by O(n), even though it isn’t obvious from any single step.

Why the total work is linear

The proof of linear time rests on an amortized analysis argument: every character comparison either extends the rightmost boundary R or fails and stops expansion at the current center. Since R only ever moves forward and is bounded by the length of the (transformed) string, the total number of successful expansions across the entire algorithm is at most O(n). Failed expansions are also bounded, one per center. Add them together and the whole algorithm — despite looking like it might do repeated work — runs in O(n) time and O(n) space for the transformed string and its radius array.

Manacher’s algorithm vs the naive approach

	Naive expand-around-center	Manacher’s algorithm
Time complexity	O(n²) worst case	O(n)
Space complexity	O(1)	O(n)
Handles odd/even length	Requires separate cases	Unified via string transformation
Reuses prior work	No — each center independent	Yes — mirrors symmetry from rightmost palindrome
Implementation complexity	Simple	Moderate

For most practical string lengths, the naive approach is easier to write correctly and fast enough. Manacher’s algorithm earns its complexity when the input can be large enough that O(n²) genuinely matters, or when the longest-palindromic-substring subproblem sits inside a tighter time budget as part of something bigger.

Where it fits among string algorithms

Manacher’s algorithm belongs to a family of linear-time string techniques that trade a more intricate invariant for asymptotic speed — the same tradeoff seen in Rabin-Karp’s rolling hash for substring search or the two-pointers technique for scanning problems generally. None of these are the first tool to reach for; they matter once profiling or input size shows that a simpler O(n²) or O(n log n) approach is the actual bottleneck.

The takeaway

Manacher’s algorithm finds the longest palindromic substring in O(n) time by transforming the string to handle odd and even-length palindromes uniformly, then reusing the symmetry of the rightmost palindrome found so far to skip redundant character comparisons at each new center. It’s a specialized tool — most codebases never need it — but it’s a clean example of how amortized analysis turns an apparently repetitive algorithm into a provably linear one.