Manacher's Algorithm (Palindromes)

Generated on 2025-07-10 02:08:28 Algorithm Cheatsheet for Technical Interviews

Manacher’s Algorithm Cheatsheet (Palindromes)

1. Quick Overview

What is it? Manacher’s Algorithm is an efficient algorithm used to find the longest palindromic substring within a given string in linear time (O(n)). It cleverly pre-processes the string and utilizes symmetry to avoid redundant palindrome checks.

When to Use it? Ideal when you need to find the longest palindromic substring (or all palindromic substrings) and performance is critical. It’s particularly useful when dealing with large strings where brute-force approaches would be too slow.

2. Time & Space Complexity

Time Complexity: O(n) - Linear, where n is the length of the string.
Space Complexity: O(n) - Linear, due to the preprocessed string and the p array storing palindrome lengths.

3. Implementation

Here’s a clean implementation in Python, Java, and C++:

Python:

def manacher(s):
    """
    Finds the longest palindromic substring using Manacher's Algorithm.

    Args:
        s: The input string.

    Returns:
        The longest palindromic substring.
    """
    t = '#'.join('^' + s + '$')  # Preprocess: add boundary characters and separators
    n = len(t)
    p = [0] * n  # Array to store palindrome lengths centered at each index
    center = 0
    right = 0
    max_len = 0
    max_center = 0

    for i in range(1, n - 1):
        mirror = 2 * center - i  # Mirror index relative to the center

        if right > i:
            p[i] = min(right - i, p[mirror])  # Utilize symmetry

        # Attempt to expand palindrome centered at i
        while t[i + (1 + p[i])] == t[i - (1 + p[i])]:
            p[i] += 1

        # If palindrome centered at i expands past right, adjust center/right
        if i + p[i] > right:
            center = i
            right = i + p[i]

        # Update max length and center if necessary
        if p[i] > max_len:
            max_len = p[i]
            max_center = i

    start = (max_center - max_len) // 2
    return s[start:start + max_len]

# Example usage
s = "babad"
longest_palindrome = manacher(s)
print(f"Longest palindrome in '{s}': '{longest_palindrome}'") # Output: "bab" or "aba"

Java:

class Manacher {
    public static String longestPalindrome(String s) {
        String t = "^#" + String.join("#", s.split("")) + "#$";
        int n = t.length();
        int[] p = new int[n];
        int center = 0, right = 0;
        int maxLen = 0, maxCenter = 0;

        for (int i = 1; i < n - 1; i++) {
            int mirror = 2 * center - i;

            if (right > i) {
                p[i] = Math.min(right - i, p[mirror]);
            }

            while (t.charAt(i + (1 + p[i])) == t.charAt(i - (1 + p[i]))) {
                p[i]++;
            }

            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }

            if (p[i] > maxLen) {
                maxLen = p[i];
                maxCenter = i;
            }
        }

        int start = (maxCenter - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }

    public static void main(String[] args) {
        String s = "babad";
        String longestPalindrome = longestPalindrome(s);
        System.out.println("Longest palindrome in '" + s + "': '" + longestPalindrome + "'");
    }
}

C++:

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

using namespace std;

string manacher(string s) {
    string t = "^#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    t += '$';

    int n = t.length();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    int maxLen = 0, maxCenter = 0;

    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * center - i;

        if (right > i) {
            p[i] = min(right - i, p[mirror]);
        }

        while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) {
            p[i]++;
        }

        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }

        if (p[i] > maxLen) {
            maxLen = p[i];
            maxCenter = i;
        }
    }

    int start = (maxCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

int main() {
    string s = "babad";
    string longestPalindrome = manacher(s);
    cout << "Longest palindrome in '" << s << "': '" << longestPalindrome << "'" << endl;
    return 0;
}

Explanation:

Preprocessing: The input string s is transformed into t by inserting ’#’ characters between each character and adding boundary characters ’^’ and ’$’. This handles both even and odd length palindromes uniformly. For example, “aba” becomes ”^#a#b#a#$”.
p Array: p[i] stores the length of the longest palindromic substring centered at index i in the transformed string t.
center and right: center is the center of the rightmost palindrome found so far, and right is the right boundary of that palindrome (center + p[center]).
Symmetry Optimization: If i is within the range of the rightmost palindrome (right > i), the palindrome length at i can be initialized using the symmetry property: p[i] = min(right - i, p[mirror]), where mirror is the mirror index of i with respect to center.
Expansion: The algorithm attempts to expand the palindrome centered at i by comparing characters around it.
Updating center and right: If the expanded palindrome centered at i extends beyond right, center and right are updated.
Finding the Longest: The algorithm keeps track of the maximum palindrome length (max_len) and its center (max_center).
Extracting the Substring: Finally, the longest palindromic substring is extracted from the original string s using max_center and max_len.

4. Common Patterns

Finding All Palindromic Substrings: Instead of just tracking the longest, you can store all palindromes found during the iterations. The p array already contains the length of each palindrome centered at each index.
Variations on Palindrome Definition: The core algorithm can be adapted for slightly different palindrome definitions (e.g., case-insensitive palindromes, palindromes allowing certain characters to be ignored). You’ll need to modify the character comparison step accordingly.
Counting Palindromic Substrings: Sum the values in the p array and divide by two.

5. Pro Tips

Preprocessing is Key: The preprocessing step is crucial for handling both even and odd length palindromes correctly. Don’t skip it!
Symmetry Exploitation: Understand how the symmetry property is used to initialize p[i]. This is the core optimization that makes Manacher’s Algorithm linear.
Boundary Cases: Pay attention to boundary conditions during the expansion step. Make sure you don’t access indices outside the bounds of the string.
Memory Usage: While the space complexity is O(n), consider using a more memory-efficient data structure for the p array if memory is a major constraint (e.g., if you know the maximum possible palindrome length is relatively small).
Integer Overflow: Be mindful of potential integer overflows when calculating 2 * center - i. Use appropriate data types (e.g., long in Java/C++) if necessary.
Avoid Redundant Calculations: Once right is greater than the current index i, the symmetry optimization prevents redundant calculations.

6. Practice Problems

LeetCode 5. Longest Palindromic Substring: Classic problem for applying Manacher’s Algorithm.
LeetCode 647. Palindromic Substrings: Find the number of palindromic substrings. You can adapt Manacher’s to count instead of just finding the longest.
LeetCode 214. Shortest Palindrome: Add characters to the beginning of a string to make it a palindrome. Manacher’s helps find the longest palindromic prefix.

7. Templates

Here are reusable templates for the Manacher’s Algorithm:

C++ Template:

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

using namespace std;

string manacher(const string& s) {
    string t = "^#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    t += '$';

    int n = t.length();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    int maxLen = 0, maxCenter = 0;

    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * center - i;

        if (right > i) {
            p[i] = min(right - i, p[mirror]);
        }

        while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) {
            p[i]++;
        }

        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }

        if (p[i] > maxLen) {
            maxLen = p[i];
            maxCenter = i;
        }
    }

    int start = (maxCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

// Example usage:
// int main() {
//     string s = "babad";
//     string longestPalindrome = manacher(s);
//     cout << "Longest palindrome: " << longestPalindrome << endl;
//     return 0;
// }

Python Template:

def manacher(s):
    """
    Finds the longest palindromic substring using Manacher's Algorithm.

    Args:
        s: The input string.

    Returns:
        The longest palindromic substring.
    """
    t = '#'.join('^' + s + '$')  # Preprocess: add boundary characters and separators
    n = len(t)
    p = [0] * n  # Array to store palindrome lengths centered at each index
    center = 0
    right = 0
    max_len = 0
    max_center = 0

    for i in range(1, n - 1):
        mirror = 2 * center - i  # Mirror index relative to the center

        if right > i:
            p[i] = min(right - i, p[mirror])  # Utilize symmetry

        # Attempt to expand palindrome centered at i
        while t[i + (1 + p[i])] == t[i - (1 + p[i])]:
            p[i] += 1

        # If palindrome centered at i expands past right, adjust center/right
        if i + p[i] > right:
            center = i
            right = i + p[i]

        # Update max length and center if necessary
        if p[i] > max_len:
            max_len = p[i]
            max_center = i

    start = (max_center - max_len) // 2
    return s[start:start + max_len]

# Example usage:
# s = "babad"
# longest_palindrome = manacher(s)
# print(f"Longest palindrome: {longest_palindrome}")

Java Template:

class Manacher {
    public static String longestPalindrome(String s) {
        String t = "^#" + String.join("#", s.split("")) + "#$";
        int n = t.length();
        int[] p = new int[n];
        int center = 0, right = 0;
        int maxLen = 0, maxCenter = 0;

        for (int i = 1; i < n - 1; i++) {
            int mirror = 2 * center - i;

            if (right > i) {
                p[i] = Math.min(right - i, p[mirror]);
            }

            while (t.charAt(i + (1 + p[i])) == t.charAt(i - (1 + p[i]))) {
                p[i]++;
            }

            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }

            if (p[i] > maxLen) {
                maxLen = p[i];
                maxCenter = i;
            }
        }

        int start = (maxCenter - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }

    // Example usage:
    // public static void main(String[] args) {
    //     String s = "babad";
    //     String longestPalindrome = longestPalindrome(s);
    //     System.out.println("Longest palindrome: " + longestPalindrome);
    // }
}

This cheatsheet provides a comprehensive and practical guide to Manacher’s Algorithm, complete with code examples, explanations, and tips for efficient implementation and usage. Remember to practice with example problems to solidify your understanding. Good luck!