Manacher's Algorithm — Stale Centre Update Bug

LeetCode 5 — Longest Palindromic Substring — is one of the most common interview problems. The O(n^2) expand-around-centre solution passes most judges. Manacher's O(n) solution demonstrates you understand linear string algorithms at a structural level, not just memorised patterns.

Manacher (1975) is not widely taught in undergraduate curricula, which means knowing it distinguishes you. The underlying technique — maintaining a rightmost boundary and exploiting mirror symmetry — is the exact same structural insight as KMP and Z-algorithm. Once you see this pattern, you recognise it everywhere.

Manacher's Algorithm — Linear-Time Palindrome Detection Without Exploding Memory

Manacher's algorithm finds all palindromic substrings in O(n) time and O(n) space by exploiting symmetry and reusing previously computed palindrome radii. The core mechanic: maintain a center c and right boundary r of the current rightmost palindrome, then for each new position i, mirror i across c to get a candidate radius from an earlier palindrome, avoiding redundant character comparisons. This transforms the naive O(n²) or O(n³) expansion into a single linear pass.

In practice, the algorithm processes each character at most twice — once when expanding beyond r, once when mirroring inside r. The palindrome radius array P[i] stores the half-length (including center) of the longest palindrome centered at i. The key invariant: if i is within r, P[i] starts at min(P[mirror], r - i), then expands greedily. This guarantees O(n) because r only moves rightward, never left.

Use Manacher when you need to count all palindromic substrings, find the longest palindrome, or precompute palindrome radii for downstream processing (e.g., string compression, bioinformatics pattern matching). It's the only linear-time solution for this problem — suffix trees or hashing approaches are either slower or probabilistic. In real systems, it's the difference between a 10ms response and a 500ms timeout on a 10⁵-character string.

The Even/Odd Problem and the Transformation

Palindromes come in two flavours: odd-length ('aba') and even-length ('abba'). Handling both cases separately doubles code complexity. Manacher's standard trick: insert a separator character between every character (and at boundaries) to convert all palindromes to odd-length.

Original: 'abba' Transformed: '#a#b#b#a#'

Now every palindrome in the original maps to an odd-length palindrome in the transformed string. '#b#b#' is the palindrome for 'bb'. '#a#b#b#a#' is the palindrome for 'abba'. We only need to handle one case.

def transform(s: str) -> str:
    return '#' + '#'.join(s) + '#'

print(transform('abba'))   # '#a#b#b#a#'
print(transform('racecar'))# '#r#a#c#e#c#a#r#'

The P Array — Palindrome Radii

For the transformed string T, we compute P[i] = the radius of the longest palindrome centred at i (not counting the centre itself). So P[i] = k means T[i-k..i+k] is a palindrome.

The length of the corresponding original palindrome is P[i] (the separator characters cancel out).

Manacher's Algorithm — Full Implementation

Manacher maintains a 'mirror window' [l, r] — the palindrome with the rightmost boundary seen so far (centre c, right edge r). For each i, if i < r, initialise P[i] from the mirror position (2*c - i). Then try to expand.

def manacher(s: str) -> str:
    T = '#' + '#'.join(s) + '#'
    n = len(T)
    P = [0] * n
    c = r = 0

    for i in range(n):
        mirror = 2 * c - i

        if i < r:
            P[i] = min(r - i, P[mirror])

        left, right = i - P[i] - 1, i + P[i] + 1
        while left >= 0 and right < n and T[left] == T[right]:
            P[i] += 1
            left -= 1
            right += 1

        if i + P[i] > r:
            c, r = i, i + P[i]

    max_len, centre = max((v, i) for i, v in enumerate(P))
    start = (centre - max_len) // 2
    return s[start : start + max_len]

print(manacher('babad'))
print(manacher('cbbd'))
print(manacher('racecar'))
print(manacher('abacabadabacaba'))

C++ Implementation of Manacher's Algorithm

For production systems in C++, the same logic applies with careful memory management. The transformed string uses vector<char> for cache locality. The algorithm returns the longest palindromic substring as a std::string.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::string manacher(const std::string& s) {
    std::vector<char> T = {'#'};
    for (char ch : s) {
        T.push_back(ch);
        T.push_back('#');
    }
    int n = T.size();
    std::vector<int> P(n, 0);
    int c = 0, r = 0;

    for (int i = 0; i < n; ++i) {
        int mirror = 2 * c - i;
        if (i < r) {
            P[i] = std::min(r - i, P[mirror]);
        }

        int left = i - P[i] - 1;
        int right = i + P[i] + 1;
        while (left >= 0 && right < n && T[left] == T[right]) {
            ++P[i];
            --left;
            ++right;
        }

        if (i + P[i] > r) {
            c = i;
            r = i + P[i];
        }
    }

    int max_len = 0;
    int centre = 0;
    for (int i = 0; i < n; ++i) {
        if (P[i] > max_len) {
            max_len = P[i];
            centre = i;
        }
    }

    int start = (centre - max_len) / 2;
    return s.substr(start, max_len);
}

int main() {
    std::cout << manacher("babad") << '\n';
    std::cout << manacher("cbbd") << '\n';
    std::cout << manacher("racecar") << '\n';
    std::cout << manacher("abacabadabacaba") << '\n';
    return 0;
}

Three Case Mirror Analysis: When to Trust the Mirror

The mirror position mirror = 2*c - i gives the palindrome radius z0 = P[mirror] at that point. However, the mirror radius may extend beyond the current right boundary r. Three cases arise:

Case 1: z0 < r - i (mirror palindrome fully inside the rightmost palindrome) P[i] = z0. No expansion needed — the palindrome is guaranteed symmetric inside the larger palindrome.

Case 2: z0 == r - i (mirror palindrome exactly touches the boundary) P[i] = z0 initially, but expansion may extend beyond r. The while loop will try to expand; if successful, the right boundary advances.

Case 3: z0 > r - i (mirror palindrome extends beyond the boundary) P[i] = r - i. The part of the mirror palindrome beyond r is not confirmed symmetric. Expansion from r outward is required.

These three cases are handled elegantly by P[i] = min(r - i, P[mirror]) when i < r.

# Example: T = '#a#b#a#b#a#'
# Let c = 5 (centre of '#a#b#a#b#a#'), P[5] = 5, r = 10
# At i = 7, mirror = 2*5 - 7 = 3, z0 = P[3] = 1
# r - i = 3, so min(3, 1) = 1 => Case 1

# At i = 9, mirror = 1, z0 = 1, r-i = 1 => Case 2
# At i = 8, mirror = 2, z0 = 0, r-i = 2 => Case 1
print("See text for explanation")

Visual P‑Array Table for Example String

Consider input s = "ababa". Transformed T = '#a#b#a#b#a#'. The P‑array for each index i:

`` Index i: 0 1 2 3 4 5 6 7 8 9 10 T[i]: # a # b # a # b # a # P[i]: 0 1 0 3 0 5 0 3 0 1 0 ` - P[3]=3: palindrome #a#b#a# corresponds to original "aba" (length 3). - P[5]=5: palindrome #a#b#a#b#a# corresponds to original "ababa" (length 5). - All even indices (separators) have even radii multiples? Actually they have radii 0,3,0,3,0? Let's correct: The above table is illustrative. For ababa`, the P array values at even indices are: 0,3,0,3,0? Wait recalc: T: # a # b # a # b # a #. Centres at characters: i=1 (a) radius1, i=3 (b) radius3, i=5 (a) radius5, i=7 (b) radius3, i=9 (a) radius1. Centres at separators: i=0 radius0, i=2 radius? T[2-1]..T[2+1] = #a# -> palindrome? Actually check: index2 is '#', left=1 (a), right=3 (b) -> a!=b so radius0. Similarly i=4 radius0? i=4 is '#', left=3 (b), right=5 (a) -> b!=a so radius0. i=6 '#', left=5 (a), right=7 (b) -> a!=b radius0. i=8 '#', left=7 (b), right=9 (a) -> b!=a radius0. i=10 radius0. So P[i] = [0,1,0,3,0,5,0,3,0,1,0]. That's the correct array.

The longest palindrome ababa (length 5) corresponds to centre i=5 with P[5]=5. Start index = (5-5)//2 = 0.

Why it's O(n) — The Rightmost Boundary Argument

The r pointer only ever moves right — never decreases. Each time we expand (the while loop), r increases. So the total number of expansions across all iterations is at most n. All other operations per iteration are O(1). Total: O(n).

This is the same argument as KMP (pointer only moves forward) and Z-algorithm (r only moves right). Recognising this pattern is key to understanding linear string algorithms.

Advantages and Disadvantages vs Expand-Around-Center

Expand-around-centre (EAC) is the O(n²) baseline: for each of ~2n centres, expand until mismatch. Manacher improves on it by reusing previous expansions.

Advantages of Manacher over EAC: - O(n) vs O(n²) time — crucial for large strings (>10⁴ characters). - Single pass produces all palindrome radii — can be reused for subqueries. - Elegant theoretical demonstration of linear string algorithms.

Disadvantages: - Higher constant factor: EAC is simpler and may be faster for small strings (<1000 characters). - Memory: O(n) extra space for P array (vs O(1) for EAC). - Complexity: harder to implement correctly; bugs in mirror logic are common. - Input must be transformed, adding overhead.

When to use Manacher: - When string length exceeds 10⁵ and you need optimal time. - When you need to answer multiple palindrome queries on the same string (e.g., count all palindromes).

When to use EAC: - Quick prototyping or interviews where O(n²) is acceptable. - When space is constrained. - When the string is very short.

Finding All Palindromic Substrings

Manacher computes all palindrome radii in one pass, so you can use P to answer queries like 'is s[l..r] a palindrome?' in O(1) after O(n) preprocessing.

def all_palindrome_lengths(s: str) -> list[int]:
    """Return length of longest palindrome centred at each position."""
    T = '#' + '#'.join(s) + '#'
    n = len(T)
    P = [0] * n
    c = r = 0
    for i in range(n):
        if i < r:
            P[i] = min(r - i, P[2*c - i])
        while i-P[i]-1 >= 0 and i+P[i]+1 < n and T[i-P[i]-1] == T[i+P[i]+1]:
            P[i] += 1
        if i + P[i] > r:
            c, r = i, i + P[i]
    # Extract only original positions (every other entry in P)
    return [P[2*i+1] for i in range(len(s))]  # odd centres

print(all_palindrome_lengths('abacaba'))
# [1, 3, 1, 7, 1, 3, 1]

Edge Cases and Common Pitfalls

Handling edge cases in Manacher is essential for production reliability. Here are the typical failures:

1. Empty string: Should return empty string. Our function works because transform('') = '#', P[0]=0, max_len=0, start=0, s[0:0] = ''.
2. Single character: transform('a') = '#a#', P[1]=1, returns 'a'. Works.
3. All identical characters: Like 'aaaa'. The algorithm must handle large radii. The while loop may expand many times but total O(n). Ensure recursion depth is not an issue (iterative is fine).
4. Very long string with no palindrome longer than 1: The algorithm will still run O(n) but each expansion step may be short. No issue.
5. Characters that could be the separator: If input contains '#', you must choose another separator or escape. The safest approach is to use a character that is not present, e.g., chr(0) for ASCII strings.

def test_manacher_edges():
    from manacher import manacher
    assert manacher('') == ''
    assert manacher('a') == 'a'
    assert manacher('aa') == 'aa'
    assert manacher('ab') in ('a', 'b')
    assert manacher('aaaa') == 'aaaa'
    assert manacher('racecar') == 'racecar'
    print('All edge cases passed')

test_manacher_edges()

Practice Problems

Sharpen your Manacher skills with these problems:

1. [LeetCode 5 – Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) – Classic problem; implement Manacher and compare with expand-around-centre.
2. [LeetCode 647 – Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/) – Count all palindromic substrings; Manacher gives O(n) solution.
3. [LeetCode 131 – Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/) – Partition string into palindromic substrings; use Manacher to precompute palindrome status for O(n²) DP.
4. [Codeforces 245H – Queries for Number of Palindromes](https://codeforces.com/problemset/problem/245/H) – Many queries on substring palindromicity; precompute P array.
5. [Codeforces 159D – Palindrome pairs](https://codeforces.com/problemset/problem/159/D) – Count pairs of palindromic substrings; Manacher helps compute palindrome endpoints.
6. [SPOJ PALIN – The Next Palindrome](https://www.spoj.com/problems/PALIN/) – Not directly Manacher, but good practice for palindrome logic.

_Tip: For problems requiring multiple queries, precompute palindrome radii with Manacher and reuse the P array._

Why Your Naive O(n³) Solution Gets You Fired in a Code Review

You've seen the brute-force approach: check every substring, verify if it's a palindrome, return the longest. That's O(n³) with a side of shame. Senior engineers don't ship that. Manacher's algorithm exists because production systems process strings at scale — think DNA sequences, log analysis, real-time chat filters. The naive approach blows up at string length 10,000. Manacher handles 100,000 characters in milliseconds. The key insight? Palindromes overlap. Once you compute one, you reuse that work. That's exactly what the P array does. It precomputes palindrome radii, then mirrors them. You're not solving new problems — you're exploiting symmetry. That's the difference between a hack and an algorithm.

// io.thecodeforge — dsa tutorial

public class PalindromeBruteForce {
    public static String longestPalindrome(String s) {
        int n = s.length();
        String longest = "";
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                if (isPalindrome(sub) && sub.length() > longest.length()) {
                    longest = sub;
                }
            }
        }
        return longest;
    }

    private static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++; right--;
        }
        return true;
    }
}

Preprocessing String Length Parity — The Trick That Saves Your Sanity

Manacher's algorithm hates two things: even-length palindromes and index-off-by-one errors. The standard fix? Insert dummy characters between every original character. For string 'abc', you produce '#a#b#c#'. Now every palindrome is odd-length, centered on real or dummy characters. This simplifies radius expansion — you expand left and right symmetrically without even/odd branching. The preprocessing doubles the string length, but that's a constant factor. The runtime stays O(n). The real win? Your P array becomes uniform. Each index stores a radius that's easy to interpret: if P[i] = 3, the palindrome at center i has length 3. No special cases. No conditional logic. Just clean, mirror-based calculations. This single trick turns a messy implementation into a teachable, maintainable solution.

// io.thecodeforge — dsa tutorial

public class StringTransform {
    public static char[] preprocess(String s) {
        int n = s.length();
        char[] transformed = new char[2 * n + 1];
        int index = 0;
        transformed[index++] = '#';
        for (int i = 0; i < n; i++) {
            transformed[index++] = s.charAt(i);
            transformed[index++] = '#';
        }
        return transformed;
    }

    public static void main(String[] args) {
        String input = "racecar";
        char[] result = preprocess(input);
        System.out.println(new String(result));
    }
}

Extending Right Boundary — The One Variable That Gates The Algorithm

Manacher's algorithm is O(n) because of a single variable: 'rightBoundary'. This marks the farthest palindrome endpoint you've seen so far. When expanding, you only compare characters beyond this boundary. Everything inside is mirror-cached. Here's the production reality: if rightBoundary never moves, you're scanning the entire string — that's O(n²). The algorithm guarantees monotonic advancement: rightBoundary only increases. Each index gets processed once. The mirror check is O(1), the expansion beyond rightBoundary is O(n) total across the run. My juniors often ask: 'But what if we need to expand both sides?' No. Once rightBoundary passes a character, you never re-expand from it. The center and radius are reused. This is why Manacher beats expand-around-center by a factor of n.

// io.thecodeforge — dsa tutorial

public class RightBoundaryTracker {
    public static int[] findPalindromes(String s) {
        char[] t = preprocess(s);
        int n = t.length;
        int[] p = new int[n];
        int center = 0, right = 0;
        for (int i = 1; i < n - 1; i++) {
            int mirror = 2 * center - i;
            if (i < right) {
                p[i] = Math.min(right - i, p[mirror]);
            }
            while (i + p[i] + 1 < n && i - p[i] - 1 >= 0
                   && t[i + p[i] + 1] == t[i - p[i] - 1]) {
                p[i]++;
            }
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
        return p;
    }

    private static char[] preprocess(String s) {
        char[] arr = new char[2 * s.length() + 1];
        int idx = 0;
        arr[idx++] = '#';
        for (char c : s.toCharArray()) {
            arr[idx++] = c;
            arr[idx++] = '#';
        }
        return arr;
    }
}

Why Manacher’s Beats O(n²) — The Mirror Property That Cuts Work in Half

Every other palindrome algorithm wastes cycles re-expanding already-known palindromes. Manacher’s doesn't. The core insight is brutally simple: once you've expanded around center C to radius R, every palindrome to the right of C is either identical to its mirror on the left or needs a small expansion. This is not magic—it's geometry.

You store the palindrome radii in an array P. When processing index i, if i is inside the current rightmost boundary, you initialize P[i] to min(P[mirror], rightBoundary - i). That single line eliminates O(n) expansions per character. Without this mirror trick, you're back to O(n²) center expansion.

The production payoff: Manacher's handles strings up to 10⁵ characters in milliseconds. Your naive O(n²) solution starts sweating at 10⁴. When you're processing real-time chat logs or DNA sequences, this difference separates a working service from a timeout disaster.

// io.thecodeforge — dsa tutorial

public class ManacherComparison {
    // O(n²) — firesale code
    static int naiveLongestPalindrome(String s) {
        int max = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    max = Math.max(max, j - i + 1);
                }
            }
        }
        return max;
    }

    static boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }

    // Manacher O(n) — the real deal
    static int manacherLongestPalindrome(String s) {
        char[] t = preprocess(s);
        int n = t.length, center = 0, right = 0;
        int[] P = new int[n];
        for (int i = 1; i < n - 1; i++) {
            int mirror = 2 * center - i;
            P[i] = (right > i) ? Math.min(P[mirror], right - i) : 0;
            while (t[i + 1 + P[i]] == t[i - 1 - P[i]]) P[i]++;
            if (i + P[i] > right) { center = i; right = i + P[i]; }
        }
        int max = 0;
        for (int p : P) max = Math.max(max, p);
        return max;
    }

    static char[] preprocess(String s) {
        char[] t = new char[s.length() * 2 + 3];
        t[0] = '^'; t[t.length - 1] = '$';
        for (int i = 0; i < s.length(); i++) {
            t[2 * i + 1] = '#'; t[2 * i + 2] = s.charAt(i);
        }
        t[t.length - 2] = '#';
        return t;
    }
}

Real-World Strings: Why Manacher Eats O(n²) for Breakfast

You deal with real data, not textbook examples. User input, DNA sequences, log files—these strings don't care about your elegant algorithm's theoretical complexity. Let's compare on a 100,000-character random string. Manacher's O(n) finishes in under 50ms. The naive O(n²) approach? It'll take roughly 10¹⁰ operations—that's 10 seconds if you're lucky, a full minute if Java's JIT isn't feeling generous.

The difference is the work per character. Manacher touches each character a constant number of times (amortized). Every expand-around-center iteration does O(n) work per center, giving you O(n²). In a microservice handling 100 requests per second, an O(n²) endpoint becomes a bottleneck that forces horizontal scaling. Manacher keeps your instance count flat.

Your job is to write code that scales. For palindrome detection, that means Manacher. Period. The O(n²) solution is for interview whiteboards and hobby projects. Everything else demands the linear-time version.

// io.thecodeforge — dsa tutorial

public class BenchmarkManacher {
    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 100_000; i++) {
            sb.append((char)('a' + (i % 26)));
        }
        String s = sb.toString();
        
        long start = System.nanoTime();
        int naiveLen = ManacherComparison.naiveLongestPalindrome(s);
        long naiveTime = System.nanoTime() - start;
        
        start = System.nanoTime();
        int manacherLen = ManacherComparison.manacherLongestPalindrome(s);
        long manacherTime = System.nanoTime() - start;
        
        System.out.printf("Naive: %d chars, %d ms%n", naiveLen, naiveTime / 1_000_000);
        System.out.printf("Manacher: %d chars, %d ms%n", manacherLen, manacherTime / 1_000_000);
    }
}