DSA Roadmap/Advanced Niche Algorithms

Manacher's Algorithm

The O(n) upgrade to expand-around-center for palindromic substrings, by reusing symmetry the same way KMP and the Z-function reuse prefix-match information. Rarely required from scratch in interviews.

~5/5Theory: 40m

Why this is here, not in the main roadmap

The "Palindromic Substrings" subtopic covers expand-around-center, which is O(n²) and is genuinely sufficient for the large majority of interview palindrome questions. Manacher's algorithm is the O(n) upgrade for the rarer case where an interviewer explicitly presses "can you avoid the quadratic blowup?" — treat it the way you'd treat KMP relative to naive substring search: a real, interesting algorithm, but one that shows up far more often in competitive programming than in a Senior FAANG coding round. It's worth knowing exists and roughly how it works; it is not worth over-indexing on being able to reproduce it flawlessly from memory under time pressure.

The insight

Expand-around-center's inefficiency comes from treating every center as if it knows nothing about its neighbors. But if you've just finished computing a long palindrome centered at c with radius r — spanning from c - r to c + r — then for any position i inside that span, its "mirror" position i' = 2c - i on the other side of the center has already been fully computed, and by the symmetry of the outer palindrome, much of i's palindrome radius can be inferred from i''s, without any new character comparisons. This is the exact same "reuse what you already know instead of recomputing from scratch" move you saw in KMP's LPS array and the Z-function — applied here to palindrome radii instead of prefix matches.

Concretely: maintain the center c and right boundary r of the rightmost palindrome discovered so far. For a new index i < r, its mirror is i' = 2c - i. You can initialize radius[i] = min(r - i, radius[i']) — the mirror's radius, capped so you never claim symmetry past the boundary you've actually verified — and then attempt to expand further from there, since anything beyond r is unverified territory. Every index's radius is set once from a mirror in O(1), and then the total number of successful expansion steps across the entire algorithm is bounded by how far r advances overall, which is at most n. That's the whole argument for O(n) — you never redo verified work, and you extend r only when you're genuinely covering new ground.

Handling odd and even length uniformly

Manacher's is usually taught (and is easiest to implement correctly) by first transforming the string so that odd- and even-length palindromes don't need separate handling. Interleave every character with a separator not present in the alphabet (commonly #), and cap the ends with sentinels to avoid bounds checks:

s = "abba" t = "^#a#b#b#a#$"

In the transformed string t, every palindrome is odd-length and centered on either an original character or a separator — an even-length palindrome in s becomes an odd-length one centered on the # between its two halves in t. This lets a single implementation handle both cases.

def manacher(s): """Returns, for each center in the transformed string, the palindrome radius. Use this to answer both 'longest palindromic substring' and 'count all palindromic substrings' in O(n).""" t = '#' + '#'.join(s) + '#' n = len(t) radius = [0] * n center = right = 0 for i in range(n): if i < right: mirror = 2 * center - i radius[i] = min(right - i, radius[mirror]) # Attempt to expand past whatever symmetry already told us. while (i - radius[i] - 1 >= 0 and i + radius[i] + 1 < n and t[i - radius[i] - 1] == t[i + radius[i] + 1]): radius[i] += 1 if i + radius[i] > right: center, right = i, i + radius[i] return radius, t def longest_palindromic_substring_manacher(s): radius, t = manacher(s) center_index = max(range(len(t)), key=lambda i: radius[i]) max_radius = radius[center_index] start = (center_index - max_radius) // 2 # map back to original string indices return s[start:start + max_radius]

You do not need to be able to re-derive the case-by-case proof of why the mirror bound (min(right - i, radius[mirror])) is always safe from first principles in an interview — that level of rigor is for a competitive-programming write-up, not a coding round. What you need is the reuse insight (palindromes are symmetric, so verified information on one side tells you about the other) and, at most, the ability to implement the template above, including the transformation step.

Complexity

Time: O(n) — amortized via the same "boundary only moves forward" argument as KMP's i pointer and the Z-function's r boundary. Space: O(n) for the transformed string and the radius array — this is the one place Manacher's is not a strict improvement over expand-around-center, which uses O(1) auxiliary space; you're trading space for a guaranteed linear time bound.

Naive vs. optimized, side by side

ApproachTimeSpaceWhen to reach for it
Brute force (check every substring)O(n³)O(1)Never in an interview — only as a mental baseline
2-D DP (dp[i][j] = is s[i..j] a palindrome)O(n²)O(n²)Rarely preferred; useful when you need random-access palindrome queries afterward
Expand around centerO(n²)O(1)Default choice for almost every interview palindrome question
Manacher's algorithmO(n)O(n)When explicitly asked for linear time, or the input size makes O(n²) infeasible

Pitfalls and interview gotchas

  • Mapping Manacher's transformed-string indices back to the original string incorrectly. The relationship between a radius in t (the #-interleaved string) and a substring length/start in s trips people up even after they understand the algorithm conceptually — work through one small example by hand (e.g. s = "aba") before trusting your index arithmetic under time pressure.
  • Reaching for Manacher's by default instead of leading with expand-around-center. Given this technique's difficulty-to-frequency ratio, that instinct reads as over-engineering more often than it reads as impressive.

Where this connects

The reuse insight behind Manacher's — verified information about one region tells you about a symmetric or overlapping region, so don't recompute it — is the same idea underlying KMP's failure function and the Z-function (see String Matching, also in this Advanced Niche Algorithms topic), just applied to palindrome radii instead of prefix matches; if the mirroring argument here felt intuitive, that's evidence you've internalized that subtopic, and if it didn't, revisiting the Z-function's boundary-reuse argument first often makes this one click.

Further Resources (Optional)

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.