Manacher's Algorithm

Share

Find the longest palindromic substring in O(n) time using Manacher's algorithm.

Example 1
Input: s="babad" → Output: "bab"
Example 2
Input: s="cbbd" → Output: "bb"

Solution Approach

Transform string with separators. Use center expansion with pre-computed radius array to avoid redundant work.

  • Transform s to T: "#a#b#a#b#" format
  • Compute p[i] = radius of palindrome centered at i using mirror property
  • Track center c and right boundary r
  • For each center, expand while T[i+j]==T[i-j]
  • Return longest palindrome from T
Java
public String longestPalindrome(String s) {
    String T = "#" + String.join("#", s.split("")) + "#";
    int n = T.length();
    int[] p = new int[n];
    int c = 0, r = 0, maxLen = 0, center = 0;
    for (int i = 0; i < n; i++) {
        int mirror = 2 * c - i;
        if (i < r) p[i] = Math.min(r - i, p[mirror]);
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && T.charAt(i+p[i]+1) == T.charAt(i-p[i]-1))
            p[i]++;
        if (i + p[i] > r) { c = i; r = i + p[i]; }
        if (p[i] > maxLen) { maxLen = p[i]; center = i; }
    }
    int start = (center - maxLen) / 2;
    return s.substring(start, start + maxLen);
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)