Data Structures & AlgorithmsLongest Palindromic Substring

Longest Palindromic Substring

LevelIntermediate

Duration75 mins

TopicLongest Palindromic Substring

3 / 4

Manacher's Algorithm (Conceptual)

The Quest for Linear Time

In the previous pages, we explored brute force O(n³) and the elegant expand-around-center O(n²) approaches. But can we do better? Can we find the longest palindromic substring in linear time O(n)?

At first glance, this seems impossible. After all, a string might contain Θ(n²) palindromic substrings—just consider "aaa...a" which has n + (n-1) + ... + 1 = n(n+1)/2 palindromes. How can we possibly account for all of them in O(n) time?

In 1975, Glenn Manacher published an algorithm that achieves exactly this. Manacher's Algorithm finds the longest palindromic substring in O(n) time and O(n) space—an asymptotically optimal solution that has stood as the definitive answer for nearly 50 years.

This page focuses on the conceptual understanding of Manacher's algorithm—the key insights that make linear time possible—rather than getting lost in implementation details.

What You Will Learn

By the end of this page, you will understand the two key innovations that enable Manacher's algorithm: the string transformation that unifies odd/even cases, and the mirror property that allows reusing previously computed palindrome lengths. You'll grasp why the algorithm runs in O(n) time despite appearing to have nested loops.

The Odd/Even Problem

In the expand-around-center approach, we handled odd and even length palindromes separately—expanding from single characters and from gaps between characters. This dual treatment adds complexity and obscures the underlying pattern.

The Challenge:

"aba" (odd) has center at index 1
"abba" (even) has center between indices 1 and 2

These two cases require different handling, making the algorithm harder to analyze and optimize.

Manacher's Elegant Solution: String Transformation

Manacher's first key insight is to transform the input string by inserting a special character (typically '#') between every pair of adjacent characters, and at both ends:

Original:    "abba"
Transformed: "#a#b#b#a#"

Original:    "aba"
Transformed: "#a#b#a#"

This transformation has a remarkable property: every palindrome in the transformed string is odd-length with a single-character center.

String Transformation Examples
Original	Transformed	Original Length	Transformed Length
"a"	"#a#"	1	3
"ab"	"#a#b#"	2	5
"aba"	"#a#b#a#"	3	7
"abba"	"#a#b#b#a#"	4	9
"racecar"	"#r#a#c#e#c#a#r#"	7	15

Why This Works:

For an original string of length n:

Transformed string has length 2n + 1
Original odd-length palindromes remain odd-length (centered on original characters)
Original even-length palindromes become odd-length (centered on # characters)

Example: "abba" → "#a#b#b#a#"

The palindrome "abba" was even-length with center between the two 'b's. In the transformed string:

The center is now the '#' between the two 'b's: #a#b#b#a# ^
The palindrome "#b#b#" has odd length 5, centered at index 4

Example: "aba" → "#a#b#a#"

The palindrome "aba" was odd-length centered at 'b'. In the transformed string:

The center remains 'b': #a#b#a# ^
The palindrome "#a#b#a#" has odd length 7, centered at index 3

Converting Back to Original Length

If a palindrome in the transformed string has length L (centered at some position), the corresponding palindrome in the original string has length ⌊L/2⌋. For example, the transformed palindrome "#a#b#a#" has length 7, and the original "aba" has length 7/2 = 3. This relationship is consistent regardless of whether the center is a '#' or an original character.

The P Array: Storing Palindrome Radii

Manacher's algorithm computes an array P where P[i] represents the "radius" of the longest palindrome centered at position i in the transformed string.

Definition of Radius:

The radius is the number of characters extending from the center to one side (not including the center). Equivalently, a palindrome of radius r centered at position i spans from index i-r to i+r.

Example: T = "#a#b#a#"

Index:    0   1   2   3   4   5   6
T:        #   a   #   b   #   a   #
P:        0   1   0   3   0   1   0

Let's verify:

P[0] = 0: Center '#', palindrome "#" (just the center)
P[1] = 1: Center 'a', palindrome "#a#" (extends 1 on each side)
P[2] = 0: Center '#', palindrome "#"
P[3] = 3: Center 'b', palindrome "#a#b#a#" (extends 3 on each side)
P[4] = 0: Center '#', palindrome "#"
P[5] = 1: Center 'a', palindrome "#a#"
P[6] = 0: Center '#', palindrome "#"

Example: T = "#a#b#b#a#"

Index:    0   1   2   3   4   5   6   7   8
T:        #   a   #   b   #   b   #   a   #
P:        0   1   0   1   4   1   0   1   0

Let's verify the key entry:

P[4] = 4: Center '#' (between the two 'b's), palindrome "#a#b#b#a#" (extends 4 on each side)

The original palindrome "abba" has length 4, and indeed P[4]/2 = 4/2 = 2... wait, that's not right. Let's recalculate.

Actually, the relationship is: original palindrome length = P[i]. The radius P[i] in the transformed string directly gives the length in the original string!

This is because for each unit of radius in the transformed string, we include one original character (and one '#').

Key Property

For the transformed string T and P array:

• P[i] = radius of longest palindrome centered at T[i] • The corresponding original palindrome has length P[i] • The longest palindromic substring in the original string has length max(P) • The center of the longest palindrome is at position i where P[i] is maximum

The Mirror Property: The Heart of Manacher's

The naive approach to computing P would expand from each center independently—O(n) centers × O(n) expansion = O(n²). This is exactly what expand-around-center does.

Manacher's second key insight is the Mirror Property: when we're inside a known palindrome, we can often determine or bound P[i] using its mirror position, avoiding redundant expansion.

The Setup:

As we process the string left to right, we maintain:

C: Center of the rightmost palindrome we've found
R: Right boundary of that palindrome (R = C + P[C])

For a new position i inside this palindrome (i.e., i < R), we define:

i': The mirror of i around center C, where i' = 2C - i

The Key Observation:

Because positions i' and i are symmetric around center C within a known palindrome, the characters around i' are mirrored around i. Therefore, P[i] is often related to P[i'].

Three Cases for Using the Mirror:

Case 1: P[i'] < R - i (Mirror Palindrome Fits Entirely Inside)

If the palindrome at i' fits entirely within the known palindrome centered at C, then by symmetry, P[i] = P[i'] exactly. No expansion needed!

        i'      C      i       R
         ↓      ↓      ↓       ↓
    ...--|------|------|------|-...
           ↖___↗     ↖___↗
         P[i'] fits   P[i] = P[i']

Case 2: P[i'] > R - i (Mirror Palindrome Extends Beyond Left Boundary)

If the palindrome at i' would extend beyond the left boundary of the known palindrome, we can only guarantee P[i] ≥ R - i. The characters beyond R are unknown—we must expand.

    L       i'      C      i       R
    ↓       ↓       ↓      ↓       ↓
    |--...--|------|------|-------|...
       ↖___________↗  ↖___________↗
        P[i'] exceeds   P[i] ≥ R - i

Case 3: P[i'] = R - i (Mirror Touches Left Boundary Exactly)

This is the boundary case where the mirror palindrome reaches exactly to L. We know P[i] ≥ R - i, but characters beyond R might extend the palindrome. Must expand.

Unified Formula

The three cases can be unified: P[i] ≥ min(P[i'], R - i). We initialize P[i] with this value, then expand only if there might be more characters matching. The beauty is that Case 1 (the most common) requires zero expansion.

Why O(n) Complexity

The algorithm appears to have nested loops—we iterate through n positions, and at each position might expand. How can this be O(n)?

The Amortized Analysis:

The key insight is that R never decreases, and each expansion increases R by at least 1.

We process the string from left to right: O(n) positions
Each time we expand, R increases
R starts at 0 and can increase to at most 2n+1 (the transformed string length)
Therefore, total expansions across all positions ≤ 2n+1

Counting Operations:

Visits to each position: Exactly n visits (one per position)
Mirror calculations: O(1) arithmetic per position = O(n) total
Expansions: Each expansion increases R by 1. Since R ≤ 2n+1 and R never decreases, total expansions ≤ 2n+1 = O(n)

Visual Proof:

Think of it this way: each character comparison during expansion "pays for itself" by extending R. Once R passes a position, we never compare that position again (we use the mirror). So each position in the string is compared at most twice:

Once when expanding rightward from some center < i
Once when its mirror value is computed or verified

Total comparisons ≤ 2n = O(n).

Comparison with Expand-Around-Center:

In expand-around-center, expanding from center i might compare the same positions that were compared from center i-1. Manacher's avoids this by tracking R and using mirrors.

Expand-Around-Center: Each center independently expands
    Center 0: compare indices 0,0 → 1,−1 (stop)
    Center 1: compare indices 1,1 → 0,2 → −1,3 (stop)
    Center 2: compare indices 2,2 → 1,3 → 0,4 (stop)  ← Indices 0,1 compared again!

Manacher's: Reuses information from previous centers
    Center 0: compare indices 0,0 → 1,−1 (stop), R=0
    Center 1: compare indices 1,1 → 0,2 → −1,3 (stop), R=3
    Center 2: inside R, use mirror, no expansion needed!

The Power of Amortization

Manacher's algorithm exemplifies amortized analysis. While any single position might require O(n) expansion, the total work across ALL positions is bounded by O(n). This is similar to how dynamic array resizing appears O(n) per resize but amortizes to O(1) per insert.

Algorithm Walkthrough

Let's trace through Manacher's algorithm on a concrete example to see the mirror property in action.

Example: s = "abba"

Step 1: Transform

T = "#a#b#b#a#"
     0 1 2 3 4 5 6 7 8

Step 2: Initialize

P = [0, 0, 0, 0, 0, 0, 0, 0, 0] (will compute)
C = 0 (center of rightmost palindrome)
R = 0 (right boundary of rightmost palindrome)

Step 3: Process each position

i = 0: T[0] = '#'

i ≥ R (0 ≥ 0), so no mirror information
Expand: T[0] = '#' matches itself (single char palindrome)
Cannot expand further (hit left boundary)
P[0] = 0, C = 0, R = 0

i = 1: T[1] = 'a'

i ≥ R (1 ≥ 0), so no mirror information
Expand: T[0]='#' vs T[2]='#' → match! P[1] = 1
Expand: T[−1] vs T[3] → out of bounds
P[1] = 1, C = 1, R = 2

i = 2: T[2] = '#'

i ≥ R (2 ≥ 2), boundary case, try expansion
Expand: T[1]='a' vs T[3]='b' → mismatch
P[2] = 0, C and R unchanged

i = 3: T[3] = 'b'

i ≥ R (3 ≥ 2), no mirror
Expand: T[2]='#' vs T[4]='#' → match! P[3] = 1
Expand: T[1]='a' vs T[5]='b' → mismatch
P[3] = 1, C = 3, R = 4

i = 4: T[4] = '#' (between the two b's)

i ≥ R (4 ≥ 4), boundary
Expand: T[3]='b' vs T[5]='b' → match! P[4] = 1
Expand: T[2]='#' vs T[6]='#' → match! P[4] = 2
Expand: T[1]='a' vs T[7]='a' → match! P[4] = 3
Expand: T[0]='#' vs T[8]='#' → match! P[4] = 4
Expand: T[−1] vs T[9] → out of bounds
P[4] = 4, C = 4, R = 8

i = 5: T[5] = 'b'

i < R (5 < 8), we can use mirror!
Mirror i' = 2C - i = 8 - 5 = 3
P[i'] = P[3] = 1
R - i = 8 - 5 = 3
Since P[i'] < R - i (1 < 3), Case 1 applies: P[5] = P[3] = 1
No expansion needed!

i = 6, 7, 8: Similar mirror cases

Final P array: [0, 1, 0, 1, 4, 1, 0, 1, 0] Maximum: P[4] = 4, original palindrome length = 4 ("abba")

Efficiency in Action

Notice how positions 5, 6, 7, and 8 required no expansion—they were all within R = 8 and their mirror palindromes fit inside. The algorithm did heavy work at position 4 (expanding to R = 8), but then reaped the benefits at subsequent positions.

The Algorithm in Pseudocode

Here's Manacher's algorithm expressed in clear pseudocode, emphasizing the logical structure over implementation details.

manacher_pseudocode.txt

Pseudocode

function manacher(s: string) -> string:
    // Step 1: Transform the string
    T = "#" + join(s characters with "#") + "#"
    n = length(T)
    
    // Step 2: Initialize P array and tracking variables
    P = array of n zeros
    C = 0    // Center of rightmost palindrome
    R = 0    // Right boundary of rightmost palindrome
    
    // Step 3: Compute P[i] for each position
    for i = 0 to n-1:
        // Use mirror if inside current palindrome
        if i < R:
            mirror = 2*C - i
            P[i] = min(P[mirror], R - i)
        
        // Attempt to expand from current P[i]
        while i + P[i] + 1 < n AND i - P[i] - 1 >= 0 
              AND T[i + P[i] + 1] == T[i - P[i] - 1]:
            P[i] = P[i] + 1
        
        // Update center and right boundary if needed
        if i + P[i] > R:
            C = i
            R = i + P[i]
    
    // Step 4: Find the maximum and extract result
    maxLen = 0
    maxCenter = 0
    for i = 0 to n-1:
        if P[i] > maxLen:
            maxLen = P[i]
            maxCenter = i
    
    // Convert back to original string indices
    start = (maxCenter - maxLen) / 2
    return s[start : start + maxLen]

Implementation Notes

Several implementation variants exist:

• Some use sentinel characters (like '^' and '$') at the boundaries to avoid explicit bounds checking • Some track the maximum during the main loop rather than in a separate pass • Some use slightly different index arithmetic for the conversion

All variants maintain the same O(n) time and O(n) space complexity.

Implementation in Code

Here's a complete, production-ready implementation of Manacher's algorithm with detailed comments explaining each step.

manacher.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
def longest_palindrome_manacher(s: str) -> str:
    """
    Find the longest palindromic substring using Manacher's algorithm.
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    
    Args:
        s: Input string
    
    Returns:
        The longest palindromic substring
    """
    if not s:
        return ""
    
    # Step 1: Transform the string
    # Insert '#' between characters and at boundaries
    # This transforms all palindromes to odd length
    T = '#' + '#'.join(s) + '#'
    n = len(T)
    
    # P[i] = radius of palindrome centered at T[i]
    P = [0] * n
    
    # C = center of the rightmost palindrome found so far
    # R = right boundary of that palindrome (R = C + P[C])
    C = 0
    R = 0
    
    # Step 2: Compute P[i] for each position
    for i in range(n):
        # If i is within the known palindrome, use mirror
        if i < R:
            mirror = 2 * C - i  # i' = C - (i - C) = 2C - i
            # Take minimum of mirror value and remaining distance to R
            P[i] = min(P[mirror], R - i)
        
        # Attempt to expand palindrome centered at i
        # P[i] gives current known radius; try to extend
        while (i + P[i] + 1 < n and 
               i - P[i] - 1 >= 0 and 
               T[i + P[i] + 1] == T[i - P[i] - 1]):
            P[i] += 1
        
        # If this palindrome extends past R, update C and R
        if i + P[i] > R:
            C = i
            R = i + P[i]
    
    # Step 3: Find the maximum palindrome
    max_len = max(P)
    max_center = P.index(max_len)
    
    # Convert back to original string
    # In transformed string, palindrome spans [max_center - max_len, max_center + max_len]
    # In original string, this corresponds to [(max_center - max_len)//2, ...]
    start = (max_center - max_len) // 2
    
    return s[start : start + max_len]
 
 
# Test the implementation
test_cases = [
    ("babad", ["bab", "aba"]),
    ("cbbd", ["bb"]),
    ("a", ["a"]),
    ("racecar", ["racecar"]),
    ("abba", ["abba"]),
    ("forgeeksskeegfor", ["geeksskeeg"]),
]
 
print("Manacher's Algorithm Testing")
print("=" * 50)
 
for s, expected in test_cases:
    result = longest_palindrome_manacher(s)
    status = "✓" if result in expected else "✗"
    print(f"{status} Input: "{s}"")
    print(f"  Result: "{result}" (Length: {len(result)})")

When to Use Manacher's Algorithm

Manacher's algorithm is the theoretically optimal solution, but that doesn't mean it's always the right choice. Let's analyze when to use each approach.

Algorithm Selection Guide
Scenario	Recommended Algorithm	Reasoning
Interview (general)	Expand Around Center	Easier to implement and explain, O(n²) is usually sufficient
Interview (asked for optimal)	Manacher's	Demonstrates deep algorithmic knowledge
String length ≤ 1,000	Expand Around Center	O(n²) = 1M operations, trivially fast
String length 10,000+	Manacher's	O(n²) = 100M+ operations, might be slow
Simple codebase	Expand Around Center	Simpler code, fewer bug opportunities
Performance-critical system	Manacher's	Linear time guarantees consistent performance
Educational context	Both	Start with expand, then optimize to Manacher's

Practical Advice

In most technical interviews, the expand-around-center O(n²) solution is perfectly acceptable and even preferred for its clarity. Only mention or implement Manacher's if specifically asked for the optimal solution, or if you're demonstrating advanced knowledge. A clean, correct O(n²) solution beats a buggy O(n) attempt.

Manacher's Algorithm Advantages

•Optimal Time Complexity — O(n) is provably optimal; you can't do better since you must read every character.
•Predictable Performance — No worst-case degradation. Every string, regardless of structure, is processed in linear time.
•Full Palindrome Information — The P array contains the longest palindrome for every center, useful for related problems.
•Elegant Theory — Demonstrates beautiful algorithmic techniques (transformation, amortization, symmetry exploitation).

Summary: Manacher's Algorithm

Manacher's algorithm is a masterpiece of algorithmic design, achieving linear time through clever use of problem structure.

Key Takeaways

•String Transformation — Inserting '#' between characters unifies odd and even palindromes, simplifying the algorithm.
•The P Array — Stores palindrome radii for each center. P[i] directly gives the length of the corresponding original palindrome.
•The Mirror Property — When inside a known palindrome, we can often determine P[i] from its mirror P[i'] without expansion.
•Three Cases — Mirror fully inside (copy), extends past boundary (use R-i as lower bound), or touches exactly (lower bound, expand).
•O(n) Amortized — Each expansion increases R, and R is bounded by 2n+1. Total work is O(n) despite nested loops.
•Practical Trade-offs — More complex to implement than expand-around-center. Use when performance is critical or optimal solution is required.

What's Next:

In the final page of this module, we'll compare all the approaches we've learned—brute force O(n³), expand-around-center O(n²), and Manacher's O(n)—analyzing their time-space trade-offs, implementation complexity, and suitability for different scenarios. You'll leave with a complete toolkit for solving palindrome problems.

Page Complete

You now understand the conceptual foundation of Manacher's algorithm. You know about string transformation, the P array, the mirror property, and why the algorithm achieves O(n) time. Next, we'll synthesize everything with a comprehensive complexity comparison.

3 / 4

Loading learning content...

Data Structures & AlgorithmsLongest Palindromic Substring

Longest Palindromic Substring

LevelIntermediate

Duration75 mins

TopicLongest Palindromic Substring

3 / 4

Manacher's Algorithm (Conceptual)

The Quest for Linear Time

This page focuses on the conceptual understanding of Manacher's algorithm—the key insights that make linear time possible—rather than getting lost in implementation details.

What You Will Learn

The Odd/Even Problem

The Challenge:

"aba" (odd) has center at index 1
"abba" (even) has center between indices 1 and 2

These two cases require different handling, making the algorithm harder to analyze and optimize.

Manacher's Elegant Solution: String Transformation

Manacher's first key insight is to transform the input string by inserting a special character (typically '#') between every pair of adjacent characters, and at both ends:

Original:    "abba"
Transformed: "#a#b#b#a#"

Original:    "aba"
Transformed: "#a#b#a#"

This transformation has a remarkable property: every palindrome in the transformed string is odd-length with a single-character center.

String Transformation Examples
Original	Transformed	Original Length	Transformed Length
"a"	"#a#"	1	3
"ab"	"#a#b#"	2	5
"aba"	"#a#b#a#"	3	7
"abba"	"#a#b#b#a#"	4	9
"racecar"	"#r#a#c#e#c#a#r#"	7	15

Why This Works:

For an original string of length n:

Transformed string has length 2n + 1
Original odd-length palindromes remain odd-length (centered on original characters)
Original even-length palindromes become odd-length (centered on # characters)

Example: "abba" → "#a#b#b#a#"

The palindrome "abba" was even-length with center between the two 'b's. In the transformed string:

The center is now the '#' between the two 'b's: #a#b#b#a# ^
The palindrome "#b#b#" has odd length 5, centered at index 4

Example: "aba" → "#a#b#a#"

The palindrome "aba" was odd-length centered at 'b'. In the transformed string:

The center remains 'b': #a#b#a# ^
The palindrome "#a#b#a#" has odd length 7, centered at index 3

Converting Back to Original Length

The P Array: Storing Palindrome Radii

Manacher's algorithm computes an array P where P[i] represents the "radius" of the longest palindrome centered at position i in the transformed string.

Definition of Radius:

The radius is the number of characters extending from the center to one side (not including the center). Equivalently, a palindrome of radius r centered at position i spans from index i-r to i+r.

Example: T = "#a#b#a#"

Index:    0   1   2   3   4   5   6
T:        #   a   #   b   #   a   #
P:        0   1   0   3   0   1   0

Let's verify:

P[0] = 0: Center '#', palindrome "#" (just the center)
P[1] = 1: Center 'a', palindrome "#a#" (extends 1 on each side)
P[2] = 0: Center '#', palindrome "#"
P[3] = 3: Center 'b', palindrome "#a#b#a#" (extends 3 on each side)
P[4] = 0: Center '#', palindrome "#"
P[5] = 1: Center 'a', palindrome "#a#"
P[6] = 0: Center '#', palindrome "#"

Example: T = "#a#b#b#a#"

Index:    0   1   2   3   4   5   6   7   8
T:        #   a   #   b   #   b   #   a   #
P:        0   1   0   1   4   1   0   1   0

Let's verify the key entry:

P[4] = 4: Center '#' (between the two 'b's), palindrome "#a#b#b#a#" (extends 4 on each side)

The original palindrome "abba" has length 4, and indeed P[4]/2 = 4/2 = 2... wait, that's not right. Let's recalculate.

Actually, the relationship is: original palindrome length = P[i]. The radius P[i] in the transformed string directly gives the length in the original string!

This is because for each unit of radius in the transformed string, we include one original character (and one '#').

Key Property

For the transformed string T and P array:

The Mirror Property: The Heart of Manacher's

The naive approach to computing P would expand from each center independently—O(n) centers × O(n) expansion = O(n²). This is exactly what expand-around-center does.

Manacher's second key insight is the Mirror Property: when we're inside a known palindrome, we can often determine or bound P[i] using its mirror position, avoiding redundant expansion.

The Setup:

As we process the string left to right, we maintain:

C: Center of the rightmost palindrome we've found
R: Right boundary of that palindrome (R = C + P[C])

For a new position i inside this palindrome (i.e., i < R), we define:

i': The mirror of i around center C, where i' = 2C - i

The Key Observation:

Because positions i' and i are symmetric around center C within a known palindrome, the characters around i' are mirrored around i. Therefore, P[i] is often related to P[i'].

Three Cases for Using the Mirror:

Case 1: P[i'] < R - i (Mirror Palindrome Fits Entirely Inside)

If the palindrome at i' fits entirely within the known palindrome centered at C, then by symmetry, P[i] = P[i'] exactly. No expansion needed!

        i'      C      i       R
         ↓      ↓      ↓       ↓
    ...--|------|------|------|-...
           ↖___↗     ↖___↗
         P[i'] fits   P[i] = P[i']

Case 2: P[i'] > R - i (Mirror Palindrome Extends Beyond Left Boundary)

If the palindrome at i' would extend beyond the left boundary of the known palindrome, we can only guarantee P[i] ≥ R - i. The characters beyond R are unknown—we must expand.

    L       i'      C      i       R
    ↓       ↓       ↓      ↓       ↓
    |--...--|------|------|-------|...
       ↖___________↗  ↖___________↗
        P[i'] exceeds   P[i] ≥ R - i

Case 3: P[i'] = R - i (Mirror Touches Left Boundary Exactly)

This is the boundary case where the mirror palindrome reaches exactly to L. We know P[i] ≥ R - i, but characters beyond R might extend the palindrome. Must expand.

Unified Formula

Why O(n) Complexity

The algorithm appears to have nested loops—we iterate through n positions, and at each position might expand. How can this be O(n)?

The Amortized Analysis:

The key insight is that R never decreases, and each expansion increases R by at least 1.

We process the string from left to right: O(n) positions
Each time we expand, R increases
R starts at 0 and can increase to at most 2n+1 (the transformed string length)
Therefore, total expansions across all positions ≤ 2n+1

Counting Operations:

Visits to each position: Exactly n visits (one per position)
Mirror calculations: O(1) arithmetic per position = O(n) total
Expansions: Each expansion increases R by 1. Since R ≤ 2n+1 and R never decreases, total expansions ≤ 2n+1 = O(n)

Visual Proof:

Once when expanding rightward from some center < i
Once when its mirror value is computed or verified

Total comparisons ≤ 2n = O(n).

Comparison with Expand-Around-Center:

In expand-around-center, expanding from center i might compare the same positions that were compared from center i-1. Manacher's avoids this by tracking R and using mirrors.

Expand-Around-Center: Each center independently expands
    Center 0: compare indices 0,0 → 1,−1 (stop)
    Center 1: compare indices 1,1 → 0,2 → −1,3 (stop)
    Center 2: compare indices 2,2 → 1,3 → 0,4 (stop)  ← Indices 0,1 compared again!

Manacher's: Reuses information from previous centers
    Center 0: compare indices 0,0 → 1,−1 (stop), R=0
    Center 1: compare indices 1,1 → 0,2 → −1,3 (stop), R=3
    Center 2: inside R, use mirror, no expansion needed!

The Power of Amortization

Algorithm Walkthrough

Let's trace through Manacher's algorithm on a concrete example to see the mirror property in action.

Example: s = "abba"

Step 1: Transform

T = "#a#b#b#a#"
     0 1 2 3 4 5 6 7 8

Step 2: Initialize

P = [0, 0, 0, 0, 0, 0, 0, 0, 0] (will compute)
C = 0 (center of rightmost palindrome)
R = 0 (right boundary of rightmost palindrome)

Step 3: Process each position

i = 0: T[0] = '#'

i ≥ R (0 ≥ 0), so no mirror information
Expand: T[0] = '#' matches itself (single char palindrome)
Cannot expand further (hit left boundary)
P[0] = 0, C = 0, R = 0

i = 1: T[1] = 'a'

i ≥ R (1 ≥ 0), so no mirror information
Expand: T[0]='#' vs T[2]='#' → match! P[1] = 1
Expand: T[−1] vs T[3] → out of bounds
P[1] = 1, C = 1, R = 2

i = 2: T[2] = '#'

i ≥ R (2 ≥ 2), boundary case, try expansion
Expand: T[1]='a' vs T[3]='b' → mismatch
P[2] = 0, C and R unchanged

i = 3: T[3] = 'b'

i ≥ R (3 ≥ 2), no mirror
Expand: T[2]='#' vs T[4]='#' → match! P[3] = 1
Expand: T[1]='a' vs T[5]='b' → mismatch
P[3] = 1, C = 3, R = 4

i = 4: T[4] = '#' (between the two b's)

i ≥ R (4 ≥ 4), boundary
Expand: T[3]='b' vs T[5]='b' → match! P[4] = 1
Expand: T[2]='#' vs T[6]='#' → match! P[4] = 2
Expand: T[1]='a' vs T[7]='a' → match! P[4] = 3
Expand: T[0]='#' vs T[8]='#' → match! P[4] = 4
Expand: T[−1] vs T[9] → out of bounds
P[4] = 4, C = 4, R = 8

i = 5: T[5] = 'b'

i < R (5 < 8), we can use mirror!
Mirror i' = 2C - i = 8 - 5 = 3
P[i'] = P[3] = 1
R - i = 8 - 5 = 3
Since P[i'] < R - i (1 < 3), Case 1 applies: P[5] = P[3] = 1
No expansion needed!

i = 6, 7, 8: Similar mirror cases

Final P array: [0, 1, 0, 1, 4, 1, 0, 1, 0] Maximum: P[4] = 4, original palindrome length = 4 ("abba")

Efficiency in Action

The Algorithm in Pseudocode

Here's Manacher's algorithm expressed in clear pseudocode, emphasizing the logical structure over implementation details.

manacher_pseudocode.txt

Pseudocode

function manacher(s: string) -> string:
    // Step 1: Transform the string
    T = "#" + join(s characters with "#") + "#"
    n = length(T)
    
    // Step 2: Initialize P array and tracking variables
    P = array of n zeros
    C = 0    // Center of rightmost palindrome
    R = 0    // Right boundary of rightmost palindrome
    
    // Step 3: Compute P[i] for each position
    for i = 0 to n-1:
        // Use mirror if inside current palindrome
        if i < R:
            mirror = 2*C - i
            P[i] = min(P[mirror], R - i)
        
        // Attempt to expand from current P[i]
        while i + P[i] + 1 < n AND i - P[i] - 1 >= 0 
              AND T[i + P[i] + 1] == T[i - P[i] - 1]:
            P[i] = P[i] + 1
        
        // Update center and right boundary if needed
        if i + P[i] > R:
            C = i
            R = i + P[i]
    
    // Step 4: Find the maximum and extract result
    maxLen = 0
    maxCenter = 0
    for i = 0 to n-1:
        if P[i] > maxLen:
            maxLen = P[i]
            maxCenter = i
    
    // Convert back to original string indices
    start = (maxCenter - maxLen) / 2
    return s[start : start + maxLen]

Implementation Notes

Several implementation variants exist:

All variants maintain the same O(n) time and O(n) space complexity.

Implementation in Code

Here's a complete, production-ready implementation of Manacher's algorithm with detailed comments explaining each step.

manacher.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
def longest_palindrome_manacher(s: str) -> str:
    """
    Find the longest palindromic substring using Manacher's algorithm.
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    
    Args:
        s: Input string
    
    Returns:
        The longest palindromic substring
    """
    if not s:
        return ""
    
    # Step 1: Transform the string
    # Insert '#' between characters and at boundaries
    # This transforms all palindromes to odd length
    T = '#' + '#'.join(s) + '#'
    n = len(T)
    
    # P[i] = radius of palindrome centered at T[i]
    P = [0] * n
    
    # C = center of the rightmost palindrome found so far
    # R = right boundary of that palindrome (R = C + P[C])
    C = 0
    R = 0
    
    # Step 2: Compute P[i] for each position
    for i in range(n):
        # If i is within the known palindrome, use mirror
        if i < R:
            mirror = 2 * C - i  # i' = C - (i - C) = 2C - i
            # Take minimum of mirror value and remaining distance to R
            P[i] = min(P[mirror], R - i)
        
        # Attempt to expand palindrome centered at i
        # P[i] gives current known radius; try to extend
        while (i + P[i] + 1 < n and 
               i - P[i] - 1 >= 0 and 
               T[i + P[i] + 1] == T[i - P[i] - 1]):
            P[i] += 1
        
        # If this palindrome extends past R, update C and R
        if i + P[i] > R:
            C = i
            R = i + P[i]
    
    # Step 3: Find the maximum palindrome
    max_len = max(P)
    max_center = P.index(max_len)
    
    # Convert back to original string
    # In transformed string, palindrome spans [max_center - max_len, max_center + max_len]
    # In original string, this corresponds to [(max_center - max_len)//2, ...]
    start = (max_center - max_len) // 2
    
    return s[start : start + max_len]
 
 
# Test the implementation
test_cases = [
    ("babad", ["bab", "aba"]),
    ("cbbd", ["bb"]),
    ("a", ["a"]),
    ("racecar", ["racecar"]),
    ("abba", ["abba"]),
    ("forgeeksskeegfor", ["geeksskeeg"]),
]
 
print("Manacher's Algorithm Testing")
print("=" * 50)
 
for s, expected in test_cases:
    result = longest_palindrome_manacher(s)
    status = "✓" if result in expected else "✗"
    print(f"{status} Input: "{s}"")
    print(f"  Result: "{result}" (Length: {len(result)})")

When to Use Manacher's Algorithm

Manacher's algorithm is the theoretically optimal solution, but that doesn't mean it's always the right choice. Let's analyze when to use each approach.

Algorithm Selection Guide
Scenario	Recommended Algorithm	Reasoning
Interview (general)	Expand Around Center	Easier to implement and explain, O(n²) is usually sufficient
Interview (asked for optimal)	Manacher's	Demonstrates deep algorithmic knowledge
String length ≤ 1,000	Expand Around Center	O(n²) = 1M operations, trivially fast
String length 10,000+	Manacher's	O(n²) = 100M+ operations, might be slow
Simple codebase	Expand Around Center	Simpler code, fewer bug opportunities
Performance-critical system	Manacher's	Linear time guarantees consistent performance
Educational context	Both	Start with expand, then optimize to Manacher's

Practical Advice

Manacher's Algorithm Advantages

•Optimal Time Complexity — O(n) is provably optimal; you can't do better since you must read every character.
•Predictable Performance — No worst-case degradation. Every string, regardless of structure, is processed in linear time.
•Full Palindrome Information — The P array contains the longest palindrome for every center, useful for related problems.
•Elegant Theory — Demonstrates beautiful algorithmic techniques (transformation, amortization, symmetry exploitation).

Summary: Manacher's Algorithm

Manacher's algorithm is a masterpiece of algorithmic design, achieving linear time through clever use of problem structure.

Key Takeaways

•String Transformation — Inserting '#' between characters unifies odd and even palindromes, simplifying the algorithm.
•The P Array — Stores palindrome radii for each center. P[i] directly gives the length of the corresponding original palindrome.
•The Mirror Property — When inside a known palindrome, we can often determine P[i] from its mirror P[i'] without expansion.
•Three Cases — Mirror fully inside (copy), extends past boundary (use R-i as lower bound), or touches exactly (lower bound, expand).
•O(n) Amortized — Each expansion increases R, and R is bounded by 2n+1. Total work is O(n) despite nested loops.
•Practical Trade-offs — More complex to implement than expand-around-center. Use when performance is critical or optimal solution is required.

What's Next:

Page Complete

3 / 4