Longest Palindromic Substring: Manacher’s Algorithm Explained with Examples

The problem of finding the Longest Palindromic Substring is a classic challenge in string algorithms. A palindrome is a string that reads the same forward and backward, like madam or racecar. While naive solutions can take quadratic time, Manacher’s Algorithm solves it in O(n), making it one of the most elegant solutions in algorithm design.

Understanding the Problem

The task is simple: given a string s, find the longest contiguous substring that is a palindrome. For example:

• Input: "babad" → Output: "bab" or "aba"
• Input: "cbbd" → Output: "bb"
• Input: "racecar" → Output: "racecar"

Naive vs Efficient Approaches

Before studying Manacher’s Algorithm, let’s briefly understand the alternatives:

• Naive Approach: Expand all substrings and check for palindrome. Time complexity: O(n^3).
• Expand Around Center: Expand from each index as middle. Time complexity: O(n^2).
• Dynamic Programming: Uses DP table for palindrome detection. Time complexity: O(n^2), space: O(n^2).
• Manacher’s Algorithm: Optimized with clever symmetry handling. Time complexity: O(n).

How Manacher’s Algorithm Works

The key idea is to avoid redundant expansion by leveraging palindrome symmetry. To simplify handling even-length and odd-length palindromes, Manacher introduces separators (like #) between characters:

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

Steps of the algorithm:

1. Transform the input string by inserting a separator between each character.
2. Maintain two variables:
   • center: the current center of the longest palindrome seen so far.
   • right: the right boundary of this palindrome.
3. Create an array P where P[i] stores the radius of palindrome centered at position i.
4. For each new character:
   • Find its mirror index relative to current center.
   • Initialize its palindrome radius using mirror’s radius if it lies within boundary.
   • Try to expand outward as long as characters match.
   • Update center and right if needed.
5. The largest P[i] corresponds to the longest palindrome.

Example Walkthrough

Let’s walk through an example: "babad"

1. Transform string → "#b#a#b#a#d#"
2. P array builds step by step as expansions succeed.
3. Found palindromes:
   • "#b#" → “b”
   • "#b#a#b#" → “bab”
   • "#a#b#a#" → “aba”
4. Longest palindrome is “bab” or “aba”.

Python Implementation of Manacher’s Algorithm

def manacher(s: str) -> str:
    # Transform string
    t = "#" + "#".join(s) + "#"
    n = len(t)
    P = [0] * n
    center = right = 0

    for i in range(n):
        mirror = 2*center - i
        if i < right:
            P[i] = min(right - i, P[mirror])
        
        # Expand
        while i + 1 + P[i] < n and i - 1 - P[i] >= 0 and t[i + 1 + P[i]] == t[i - 1 - P[i]]:
            P[i] += 1
        
        # Update center and right boundary
        if i + P[i] > right:
            center, right = i, i + P[i]
    
    # Find max palindrome length
    max_len = max(P)
    center_index = P.index(max_len)
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

# Example usage
print(manacher("babad"))  # "bab" or "aba"
print(manacher("cbbd"))   # "bb"

Visual Output of Algorithm

Consider the example input: "cbbd".

• Transformed: "#c#b#b#d#"
• P array builds to show maximum radius at “bb”.

Complexity Analysis

Manacher’s Algorithm is highly efficient:

• Time Complexity: O(n), since each expansion is checked at most once.
• Space Complexity: O(n) for transformed string and radius array.

Key Takeaways

• Naive solutions are costly; Manacher achieves linear time.
• Transformation step with delimiters helps unify even and odd palindromes.
• The algorithm leverages palindrome symmetry to save computations.
• Widely used in competitive programming and advanced algorithm challenges.

Interactive Exercise

Try to run the provided Python code with different strings like racecar, aacabdkacaa, and banana. Observe how symmetry helps cut down unnecessary work by reusing previously computed results.

Conclusion

Finding the longest palindromic substring efficiently is a beautiful example of algorithmic creativity. Manacher’s Algorithm provides a linear-time solution, demonstrating the power of symmetry exploitation in strings. It remains a must-know for anyone serious about algorithms and competitive programming.