## DEV Community

ozlab

Posted on • Updated on

# The Longest Palindromic Sub-string

I saw this problem on LeetCode couple of years ago: Longest Palindromic Substring

I used to browse problems on LeetCode every time before I was seeking for a new job. But, you know, it's pretty relaxing. I mean, if I found that i couldn't solve a problem easily, I just gave up. No pressure.

Take this Longest Palindromic Substring for example, I met it a few times before, I knew there is an algorithm called Manacher can solve this. But I've never worked it out even though I knew about the algorithm. Let me try again today.

The first idea came into my head was, find all the palindromic sub-strings and check their lengths. It sounds like crazy but it's actually a viable plan. To make it work, we need to check each character and find out the palindromic sub-string that centered with this character. We can store the "radius" of the palindromic sub-string for each character in the original string, then find out the longest one. So the radius obvious can be 1 or more.

For example, for the character d in string

``````a b c d c b x
``````

the radius is 3 (d, c, b). For character b, its radius is 1 (only including b itself).

The problem is, for a super long string, calculating the radius for each palindromic string is not efficient. We have to find a way to avoid always accumulating the radius from 1.

The Manacher's algorithm is based on this idea.

### Diagram 1

• We are going to find out the longest palindromic sub-string in a string `s`
• We go through each character from left to right, and put the radius of the palindromic sub-string (which centered with the current character) into an array `P`.
• So far the radius (on the right) of the palindromic sub-string with the centre character `s[idx]` can reach the position `maxRight`, which is the most right position among all the palindromic sub-strings.
• At the moment we are at the character `s[i]`. We are going to find the radius of Pi and save it in `P[i]`.

Before we start, we need to handle this issue first: if a palindromic string has even number of characters, the centre of it is a space between two characters

If a string has odd number of character(s), the centre is a character:

So the first step of this Manacher algorithm is, eliminating this ambiguity by inserting an arbitrary character (that doesn't appear in the string), say "#", between every two characters of the string:

### Diagram 2

• When i < maxRight, the whole Pi or part of Pi has a "mirror" on the other side of `idx`. This "mirror" is Pj. Its centre character is s[j].
• If `P[j]` is relatively small - the whole Pj is included in Pidx (See Diagram 1): We find the initial value of `P[i]`. That is, `P[i] = P[j]`. Then with `i` as the centre, we expand Pi until it's not palindromic any more or reach the end of `s`.
• If `P[j]` is relatively large - part of Pj is outside Pidx (See Diagram 2): The initial value of `P[i]` is `maxRight - i`. Then with `i` as the centre, we expand Pi until it's not palindromic any more or reach the end of `s`.
• When i > maxRight, it means there is no history record can be used to calculate Pi, so `P[i]` will start from 1.

So the critical part of this algorithm: what is the initial value of `P[i]`? The answer is:

``````P[i] = min(P[j], maxRight - i);
``````

And here's how to get `P[j]`: From Diagram 1 we can easily get that `idx - j = i - idx`, so `j = 2 * idx -i`.

Now we know the position of the longest palindromic sub-string centre and its radius, so we can get its start position and then work out what this sub-string is. The following code is what I submitted to Leetcode, I'm happy with the 12 ms runtime and 10 MB memory used.

``````class Solution {
public:
string longestPalindrome(string s) {
string retStr = s;
int newLen = s.length() * 2 + 1;

// First step: Insert "#" to make the string size an odd number
for (int i = 0; i < newLen; i += 2)
{
retStr = retStr.insert(i, "#");
}
retStr.insert(0, "\$");

// Process retStr
vector<int> p(retStr.size(), 0);
int mx = 0, id = 0, resLen = 0, resCenter = 0;
for (int i = 1; i < retStr.size(); ++i) {
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (retStr[i + p[i]] == retStr[i - p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (resLen < p[i]) {
resLen = p[i];
resCenter = i;
}
}
return s.substr((resCenter - resLen) / 2, resLen - 1);
}
};
``````

from: OZLab