Manacher’s Algorithm

and 5. Longest Palindromic Substring

Discovered by Glenn Manacher in 1975.

Manacher’s Algorithm is a linear time (O(n)) method to find the longest palindromic substring in a string.

It is the fastest possible solution for this problem and the only known O(n) algorithm.

Why was it invented?

Normal methods expand around each center → O(n²).
Manacher fixes this by:

Not expanding from scratch every time
Reusing information from previously computed palindromes
Using the symmetry of palindromes

The idea in 10 seconds (super simple)

Put a # between letters

Because normally we have:

• odd palindromes → racecar
• even palindromes → abba

These make logic messy.

So convert:

abba → #a#b#b#a#
racecar → #r#a#c#e#c#a#r#

Now every palindrome is centered on a character.
Life becomes easy.

For each character, store radius of palindrome

Example:

# a # b # b # a #
0 1 0 3 0 3 0 1 0  ← these are radii

p[i] = how far the palindrome expands around position i.

Use the mirror trick

If you have a palindrome centered at C, and you're now checking a position i inside that palindrome, then:

mirror = 2*C - i

This “mirror index” on the left side already tells you a lot about the palindrome on the right side.

Get Aakansha A’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

So instead of expanding from scratch (slow),
you directly copy the radius from the mirror.

Only expand after that if needed.

This saves a TON of time → making the algorithm linear.

Track the farthest right boundary

Manacher tracks:

• center → the center of the rightmost palindrome found
• right → how far that palindrome extends

If the current index i is within the right boundary,
Manacher uses the mirror to skip useless comparisons.

The magic effect

Because of the mirror speed-up:
you don’t re-check characters that you already matched earlier.

So instead of O(n²) expansions,
you do at most O(n) expansions to

Final output

After building the radius array, you:

1. find the index with the largest radius
2. convert that index back to original string indices
3. return the substring

Manacher’s Algorithm = Transform string + use palindrome symmetry + mirror reuse → O(n) longest palindrome.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        # Step 1: Transform
        t = "#" + "#".join(s) + "#"
        n = len(t)
        
        # Array to store radius of palindrome around each index
        p = [0] * n  
        
        center = 0
        right = 0
        
        # Step 2: Manacher
        for i in range(n):
            mirror = 2*center - i   # mirror index of i
            
            if i < right:
                p[i] = min(right - i, p[mirror])
            
            # expand around i
            a = i + (1 + p[i])
            b = i - (1 + p[i])
            
            while a < n and b >= 0 and t[a] == t[b]:
                p[i] += 1
                a += 1
                b -= 1
            
            # Update center and right boundary
            if i + p[i] > right:
                center = i
                right = i + p[i]
        
        # Step 3: Find longest
        max_len = max(p)
        idx = p.index(max_len)
        
        start = (idx - max_len) // 2   # convert back to original string index
        return s[start:start+max_len]