Manacher's Algorithm

Manacher's Algorithm (hard)

Manacher’s Algorithm finds the longest palindromic substring in linear time by reusing previously computed palindrome information. Instead of expanding from every center, it mirrors results around a known palindrome and only expands when necessary. This eliminates redundant work and makes the algorithm extremely efficient and elegant.

Core Idea

The Length of the palindromic substring on the left side will be equal to the length of the substring on the right side.

I to R-1 is a mirror,
We only need to explore elements >= R

🪞 Step-by-Step Breakdown

1. Transform the string:

   • Insert # between characters (and at ends) to handle even-length palindromes.

   • Example: "abba" becomes "#a#b#b#a#".

2. Initialize variables:

   • p[i]: radius of palindrome centered at i.

   • l, r: current left and right boundaries of the known palindrome.

   • maxLen, center: track the longest palindrome found.

3. Iterate through the transformed string:

   • If i > r, start fresh (k = 0).

   • Else, use the mirror of i to guess p[i].

     • If the mirror palindrome fits completely inside the known boundaries. You can directly copy its length.

     • Else, if the mirror goes out of the known range, expand outward from the unknown part.

   • Expand around i while characters match.

   • Update l and r if the new palindrome goes beyond r.

4. Extract the result:

   • Use center and maxLen to get the original substring from s.

🧩 Why It’s Efficient

Instead of checking every possible center, it reuses previously computed information using symmetry. That’s the magic of Manacher’s.

5. Longest Palindromic Substring

class Solution {
    string transform(string &s){
        string t = "#";
        for(auto c : s){
            t += c;
            t += "#";
        }
        return t;
    }
public:
    string longestPalindrome(string s) {
        string t = transform(s);
        int n = t.size();
        vector<int> p(n);

        int l = 0, r = 0, k;
        int maxLen = 0, center;
        p[0] = 0;
        for(int i = 1; i<n; ++i){
            if(i > r){
                k = 0;
            }
            else{
                int j = l + (r - i);
                if(j - p[j] > l){
                    p[i] = p[j];
                    continue;
                }
                else{
                    k = r - i;
                }
            }

            while(i-k >= 0 && i + k < n && t[i-k] == t[i+k]){
                k++;
            }
            k--;

            p[i] = k;
            if(p[i] > maxLen){
                maxLen = p[i];
                center = i / 2;
            }

            if(i + k > r){
                l = i - k;
                r = i + k;
            }
        }

        return s.substr(center - maxLen / 2, maxLen);
    }
};