Manacher's Algorithm: Longest Palindromic Substring

Key Insights

Manacher’s algorithm achieves O(n) time complexity by exploiting palindrome symmetry—information about palindromes on the left side of a center can be mirrored to skip redundant comparisons on the right side.
The string transformation trick (inserting separators like #) unifies odd and even-length palindrome handling into a single, elegant algorithm.
Despite appearing to have nested loops, the algorithm is linear because the right boundary only moves forward—each character is visited at most twice.

The Problem: Finding the Longest Palindrome

Given a string, find the longest substring that reads the same forwards and backwards. This classic problem appears everywhere: text editors implementing “find palindrome” features, DNA sequence analysis looking for biological palindromes, and data compression algorithms identifying repetitive patterns.

The naive approach checks every possible substring and verifies if it’s a palindrome—O(n³) time complexity that becomes unusable for strings longer than a few thousand characters.

def longest_palindrome_naive(s: str) -> str:
    def is_palindrome(sub: str) -> bool:
        return sub == sub[::-1]
    
    n = len(s)
    longest = ""
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if is_palindrome(substring) and len(substring) > len(longest):
                longest = substring
    return longest

The expand-around-center approach improves this to O(n²) by treating each character (and gap between characters) as a potential palindrome center, then expanding outward. This is the solution most developers reach for in interviews:

def longest_palindrome_expand(s: str) -> str:
    def expand(left: int, right: int) -> str:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]
    
    longest = ""
    for i in range(len(s)):
        # Odd-length palindromes
        odd = expand(i, i)
        if len(odd) > len(longest):
            longest = odd
        # Even-length palindromes
        even = expand(i, i+1)
        if len(even) > len(longest):
            longest = even
    return longest

For most practical purposes, O(n²) is acceptable. But when processing millions of characters—genome sequences, log files, or real-time text streams—you need Manacher’s algorithm and its O(n) guarantee.

The Key Insight: Palindrome Symmetry

Here’s what makes Manacher’s algorithm brilliant: palindromes are symmetric by definition. If you’ve already computed palindrome information for the left half of a known palindrome, you can often mirror that information to the right half without recomputing.

Consider the string "abaXaba". Once you discover the full palindrome centered at X, you know that position 5 (a) mirrors position 1 (a). If you already computed that position 1 is the center of a palindrome of radius 1, position 5 likely has the same property.

Before diving into the algorithm, we need to handle a practical issue: odd-length and even-length palindromes behave differently. The transformation trick solves this elegantly by inserting separator characters:

def transform(s: str) -> str:
    """Transform string to handle odd/even palindromes uniformly.
    
    'abc' → '#a#b#c#'
    'abba' → '#a#b#b#a#'
    """
    return '#' + '#'.join(s) + '#'

# Original: "aba" (odd, length 3, center at index 1)
# Transformed: "#a#b#a#" (length 7, center at index 3)

# Original: "abba" (even, length 4, center between indices 1-2)  
# Transformed: "#a#b#b#a#" (length 9, center at index 4 which is '#')

After transformation, every palindrome has odd length with a clear center character. The # symbols act as virtual centers for originally even-length palindromes.

Algorithm Mechanics: Center and Right Boundary

Manacher’s algorithm maintains two critical variables as it scans left to right:

center: The center of the palindrome that extends furthest to the right
right: The right boundary of that palindrome (exclusive)

For each position i, we also track p[i]: the radius of the longest palindrome centered at i (not including the center itself).

The algorithm exploits the mirror property. If position i falls within the current rightmost palindrome (i.e., i < right), we can look at its mirror position mirror = 2 * center - i and use p[mirror] as a starting point.

Three cases emerge:

def manacher_core_logic(t: str) -> list:
    """Core Manacher logic showing the three cases."""
    n = len(t)
    p = [0] * n  # p[i] = radius of palindrome centered at i
    center = 0
    right = 0
    
    for i in range(n):
        if i < right:
            mirror = 2 * center - i
            
            # Case 1: Mirror palindrome fits entirely within current boundary
            # Case 2: Mirror palindrome extends to or beyond left boundary
            # We take the minimum to be safe, then expand
            p[i] = min(right - i, p[mirror])
        
        # Case 3 (or continuation): Expand around center i
        # This also handles when i >= right (no mirror info available)
        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
        
        # Update center and right if this palindrome extends further
        if i + p[i] > right:
            center = i
            right = i + p[i]
    
    return p

The key insight: when the mirror palindrome fits entirely within the current boundary, we can directly copy its radius. When it doesn’t, we use what we can and expand from there.

Complete Implementation

Here’s the full, production-ready implementation:

def longest_palindromic_substring(s: str) -> str:
    """Find the longest palindromic substring using Manacher's algorithm.
    
    Time: O(n), Space: O(n)
    """
    if not s:
        return ""
    
    # Transform: "abc" → "^#a#b#c#$"
    # ^ and $ are sentinels to avoid boundary checks
    t = '^#' + '#'.join(s) + '#$'
    n = len(t)
    p = [0] * n
    
    center = 0
    right = 0
    
    for i in range(1, n - 1):  # Skip sentinels
        if i < right:
            mirror = 2 * center - i
            p[i] = min(right - i, p[mirror])
        
        # Attempt expansion
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        
        # Update rightmost palindrome
        if i + p[i] > right:
            center = i
            right = i + p[i]
    
    # Find the maximum element in p
    max_len = max(p)
    center_index = p.index(max_len)
    
    # Convert back to original string indices
    # In transformed string, actual chars are at odd indices
    # Original start = (center_index - max_len) // 2
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

function longestPalindromicSubstring(s) {
    if (!s) return "";
    
    // Transform with sentinels
    const t = `^#${s.split('').join('#')}#$`;
    const n = t.length;
    const p = new Array(n).fill(0);
    
    let center = 0, right = 0;
    
    for (let i = 1; i < n - 1; i++) {
        if (i < right) {
            const mirror = 2 * center - i;
            p[i] = Math.min(right - i, p[mirror]);
        }
        
        while (t[i + p[i] + 1] === t[i - p[i] - 1]) {
            p[i]++;
        }
        
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    
    const maxLen = Math.max(...p);
    const centerIndex = p.indexOf(maxLen);
    const start = Math.floor((centerIndex - maxLen) / 2);
    
    return s.substring(start, start + maxLen);
}

Complexity Analysis: Why It’s Actually O(n)

The nested while loop inside the for loop looks suspicious—shouldn’t this be O(n²)? The key is amortized analysis.

The right boundary only moves forward, never backward. Each expansion of p[i] moves right further to the right by exactly one position per comparison. Since right can move at most n positions total across the entire algorithm, the total number of character comparisons is bounded by 2n: at most n comparisons that successfully expand (moving right forward) and at most n comparisons that fail (one per position).

Space complexity: O(n) for the transformed string and the p array.

Finding all maximal palindromic substrings becomes trivial once you have the p array:

def all_palindromic_substrings(s: str) -> list:
    """Return all maximal palindromic substrings."""
    if not s:
        return []
    
    t = '^#' + '#'.join(s) + '#$'
    n = len(t)
    p = [0] * n
    center = right = 0
    
    for i in range(1, n - 1):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    
    result = []
    for i in range(1, n - 1):
        if p[i] > 0:
            length = p[i]
            start = (i - length) // 2
            result.append(s[start:start + length])
    
    return list(set(result))  # Remove duplicates

Related but different: The longest palindromic subsequence problem (characters don’t need to be contiguous) requires dynamic programming with O(n²) time—Manacher’s algorithm doesn’t apply.

Summary: When to Use Manacher’s

Approach	Time	Space	When to Use
Brute Force	O(n³)	O(1)	Never in production
Expand Center	O(n²)	O(1)	Interviews, small inputs
Manacher’s	O(n)	O(n)	Large inputs, performance-critical

Interview tips: Most interviewers expect the expand-around-center solution. If you mention Manacher’s, be prepared to explain the mirror property clearly. The transformation trick is the easiest part to remember; the center/right boundary tracking is where candidates stumble.

Practice problems: LeetCode #5 (Longest Palindromic Substring), LeetCode #647 (Palindromic Substrings), LeetCode #214 (Shortest Palindrome—uses Manacher’s or KMP).

Manacher’s algorithm exemplifies a powerful pattern in algorithm design: when you spot symmetry in your problem structure, exploit it ruthlessly. The 30 minutes spent understanding this algorithm pays dividends whenever you encounter palindrome-related problems at scale.