Manacher's Algorithm (All Palindromes in O(n))

This is an extension topic beyond most interviews: expand-around-center (O(n^2)) is the expected answer for palindromic substrings, and Manacher pays off as the follow-up when n reaches 10^5 or more, or when a hard problem needs the palindrome radius at every center.

Intuition

Every palindrome has a center: a character (odd length) or a gap between two characters (even length). If the longest palindrome around a center has length L, then trimming one character from each end gives palindromes of length L - 2, L - 4, and so on. So one number per center, its radius, describes every palindrome in the string, even though there can be O(n^2) of them.

To treat odd and even centers alike, insert a separator: "aba" becomes t = "#a#b#a#". Now every palindrome of s is an odd-length palindrome of t centered at a character or a #.

The speed-up is mirroring. Keep the palindrome of t that reaches farthest to the right, t[l:r]. For a new center i < r, its mirror j = l + r - 1 - i was computed already, and inside the big palindrome the neighborhood of i is a reflection of the neighborhood of j. So the radius at i is at least min(p[j], r - i); only characters beyond r need direct comparison, and each such comparison moves r right. r never moves back, so the whole scan is O(n).

When to use it in interviews / OAs

• Longest palindromic substring when n is large, or as the "can you do better than O(n^2)?" follow-up.
• Counting palindromic substrings in O(n).
• Many "is s[l:r] a palindrome?" queries: O(1) each after one O(n) pass (hashing also works but is probabilistic).
• Hard problems built on per-center radii: maximum product of two non-overlapping odd palindromes, shortest palindrome by adding characters (a palindromic prefix is a palindrome that touches index 0).

Template

Radii on the separated string

def manacher(s: str) -> list[int]:
    # t = "#a#b#...#"; p[i] = arm length so that t[i - p[i] + 1 : i + p[i]] is a palindrome
    t = "#" + "#".join(s) + "#"
    n = len(t)
    p = [0] * n
    l = r = 0  # t[l:r] is the palindrome reaching farthest right
    for i in range(n):
        k = min(p[l + r - 1 - i], r - i) if i < r else 1  # start from the mirror's radius
        while i - k >= 0 and i + k < n and t[i - k] == t[i + k]:
            k += 1
        p[i] = k
        if i + k > r:
            l, r = i - k + 1, i + k
    return p

The palindrome of t around index i corresponds to a palindrome of s of length p[i] - 1 starting at index (i - p[i] + 1) // 2.

What you can read off the radii

def longest_palindrome_manacher(s: str) -> str:
    p = manacher(s)
    i = max(range(len(p)), key=p.__getitem__)
    start = (i - p[i] + 1) // 2
    return s[start:start + p[i] - 1]


def count_palindromic_substrings(s: str) -> int:
    # center i in t contributes palindromes of lengths p[i] - 1, p[i] - 3, ... > 0
    return sum(k // 2 for k in manacher(s))


def palindrome_checker(s: str):
    p = manacher(s)

    def is_pal(l: int, r: int) -> bool:  # is s[l:r] a palindrome? (l < r)
        return p[l + r] - 1 >= r - l  # its center in t sits at index l + r

    return is_pal

Complexity

O(n) time and O(n) memory: the separated string has 2n + 1 characters and every successful comparison advances r. Each query on top is O(1).

For comparison, expand-around-center is O(n^2) time and O(1) memory; it is shorter to write and is what most interviewers expect first.

Common pitfalls

• Forgetting the even case. Without separators (or a second array for even centers), palindromes like "abba" are missed.
• Index conversion. Lengths and start positions in s come from the formulas above; off-by-one errors here are the usual bug, so test "a", "aa", "aba" and the empty string.
• Separator characters. The # must not occur in s. Since it is only compared with itself at even positions, any character absent from s works.
• Mirror outside the window. Use min(p[mirror], r - i); trusting p[mirror] blindly copies information about characters that lie beyond the known palindrome.
• Counting palindromes as distinct strings. count_palindromic_substrings counts occurrences (positions). Distinct palindromes need a different structure (a palindromic tree), beyond interview scope.

Interview variations

• Longest palindromic substring / palindromic substrings count. The two helpers above.
• Palindrome partitioning (minimum cuts). Precompute is_pal in O(n) instead of an O(n^2) table, then run the usual DP.
• Shortest palindrome by adding characters in front. Find the longest palindromic prefix: the largest p[i] whose palindrome starts at index 0 of t; KMP on s + "#" + reverse(s) is the classic alternative.
• Maximum product of two non-overlapping odd palindromes. Odd radii from Manacher, then prefix and suffix maxima of "longest palindrome ending by / starting from each index".
• Hashing alternative. Forward and reverse rolling hashes answer palindrome queries in O(1) with a small error probability, and combine with binary search for the longest palindrome around each center in O(n log n).