Manacher’s Algorithm for Longest Palindromic Substring

Longest Palindromic Substring has a straight-forward description [1]:

Given a string s, return the longest palindromic substring in s.

The goal of this article is to understand how to solve it using the tricky Manacher’s algorithm.

A naive method iterates all the element and then expands from the center to check whether it is a palindrome. This method’s time complexity is O(n²) because it expands from scratch for every element.

Compared to that naive method, Manacher’s algorithm reuses the information from the expansion process. Manacher’s algorithm is the best solution because its time complexity and space complexity are O(n) .

The Key Insight

If we know a palindrome centered at C with right boundary R, then for any index i inside this palindrome (i < R), its mirror j = 2 * C - i has the same symmetry.

Step 1: Transform

This step converts the original string s1to s2 , to avoid handling odd and even cases.

Step 2: Set up

We use C ,R , and P to keep track of the information of the previous interation.

Step 3: Walk through each index

At the index i = 0 , it just does nothing.

Now we are at index i = 1. There is a formula for mirror:

mirror = 2 * C - i  # C = 0, i = 1

Here mirror = -1 is outside the string, so we ignore it. We do not have shortcut information to reuse yet. So, we expand around i = 1 .

Start with radius = 0
Look at the left i-1=0 and right i+1=2
The left char and the right char are both # , so they match. Increase radius to 1.

Now radius = 1 means palindrome = #a# . Then try expanding further. Then the left = i - 2 = -1 is out of buids, so stop expanding. The final expansion result is:

P[1] = 1

Therefore, we have the information for the palindrome here:

Right boundary = i + P[i] = 2

Then update center and right boundary (of the rightmost palindrome):

C = 1
R = 2

Now we move to i = 2.

First we calculate mirror = 0:

mirror = 2 * C - i  # C = 1, i = 2

Then we check if i is inside R (i < R ). But:

i = 2
R = 2

The answer is no, which means, there is no calculation information that we can reuse.

So we expand again. Start radius = 0 and the left and the right do not match. Thus:

P[2] = 0

Then we update center and right boundary. Its right boundary = i + P[i] = 2 , which is not greater than current R. So we do not update C and R .

Now we are at index 3.

(1) Mirror index

mirror = -1 (no reusable info):

mirror = 2 * C - i  # C = 1, i = 3

(2) Inside the current right boundary?

Check i < R is false. So we cannot set the upper bound of P[i] using the mirror.

(3) Expand

P[3] = 1

(4) Update center and right

Its right boundary = i + P[i] = 4 , which is greater than current R. So update:

C = 3
R = 4

Now we are at index 4.

(1) Mirror index

mirror = 2:

mirror = 2 * C - i  # C = 3, i = 4

(2) Inside the current right boundary?

No (cannot get a free starting radius from the mirror). We will expand from scratch.

(3) Expand

P[4] = 4

(4) Update center and right

Its right boundary = i + P[i] = 4 , which is greater than current R. So update:

C = 4
R = 8

Now we are at index 5.

(1) Mirror index

mirror = 3:

mirror = 2 * C - i  # C = 4, i = 5

(2) Inside the current right boundary?

Yes.

So we can start with:

P[5] = min(R - i, P[mirror]) = min(3, 1) = 1

Let us look carefully at this magical formula.

So, first we are trying to “steal” the information from P[mirror] . However, P[mirror] might calculate some elements that beyond the range of the rightmost palindrom. Note that the current index does not have these elements on its right side. Therefore, we use R - i to consider this case. Imagine the worst case. If R - i = 0 , then the index reach to the rightmost end. In this case, there is no “free radius” that the current index can still — you have to expand it from scratch.

(3) Expand (from the starting radius)

P[5] = 1

(4) Update center and right

Its right boundary = i + P[i] = 6 , which is not greater than current R. So stay the same.

Now we are at index 6.

(1) Mirror index

mirror = 2:

mirror = 2 * C - i  # C = 4, i = 6

(2) Inside the current right boundary?

Yes. Start with P[6]=0.

(3) Expand

P[6] = 0

(4) Update center and right

No update.

The same logic applies to index 7 and 8.

Step 4: Find max radius

During the iteration, we can use a variable best_center to record the largest P[i] , then build the substring afterwards.

The C++ implementation

class Solution {
public:
    string longestPalindrome(string s) {
        string t = transformString(s);
        int n = t.size();
        vector<int> P(n, 0);

        int C = 0;   // center
        int R = 0;   // right boundary
        int best_len = 0;
        int best_center = 0;

        for (int i = 0; i < n; i++) {
            int mirror = 2 * C - i;
            // steal or not
            if (i < R) {
                P[i] = min(R - i, P[mirror]);
            }
            // try to expand
            int radius = P[i] + 1;
            while (i - radius >= 0 && i + radius < n && t[i - radius] == t[i + radius]) {
                P[i]++;
                radius = P[i] + 1;
            }
            // update center & R
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
            // track the best palindrome found
            if (P[i] > best_len) {
                best_len = P[i];
                best_center = i;
            }
        }

        int start = (best_center - best_len) / 2;  // map back to original indices
        return s.substr(start, best_len);
    }

private:
    string transformString(const string& s) {
        string t = "#";
        for (char c : s) {
            t += c;
            t += "#";
        }
        return t;
    }
};

More Notes

Why It works in O(n)?

At first glance, it might be astounding that this works in O(n).

Every index either reuses mirror information in O(1), or causes an expansion that moves the right boundary R forward.

Importantly, each time we expand a palindrome past R, we push R forward. Once R has passed a character, that character will never be checked in an expansion again — because expansions only ever go beyond the current R. So across the entire algorithm, R can advance at most n steps (the length of the string). That means all the “extra expansion work” sums up to O(n) overall.

Why Track Only the Rightmost palindrome?

The truth is: we can only “steal” the information from the rightmost palindrome. If it is not the rightmost palindrome, the current index is definitely out of its reach.

If you found this article helpful, please show your support by clicking the clap icon 👏 and following me 🙏. Thank you for taking the time to read it, and have a wonderful day!

References

Post Views: 13

September 1, 2025

hyl3d

Algorithm

HeYulong 3D

Manacher’s Algorithm for Longest Palindromic Substring