Longest Palindromic Substring With Manachar’s Algorithm
LeetCode: Given a string s, find the longest palindromic substring in s.
What is a Palindrome?
A palindrome is a word that reads the same forwards and backwards. In my universe, there are two kinds of palindrome: “Odd Pal” and “Even Pal”.
Even Pal
Even Pal is a palindrome which has an even length, for example: “ZYXXYZ”. In the visualization below you can see how we can split it into 2 parts that have size 3: “ZYX” and “XYZ” . This palindrome will always have two centres called “Left Center” at index2 and “Right Center” at index3.
Notice that:
- character at index2 = character at index3 (mirror 1)
- character at index1 = character at index4 (mirror 2)
- character at index0 = character at index5 (mirror 3)
It is because of the above equality of characters at their respective indexes that the string is a palindrome and the two parts look like a sequence of 3 mirrors.
Odd Pal
Odd Pal is a palindrome which has an odd length, example: “ZYXWXYZ”. In the visualization below you can see how we can split the string into 2 parts that have size 3: “ZYX” and “XYZ”, while “W” at index3 becomes the center.
Notice that:
- character at index2 = character at index4 (mirror 1)
- character at index1 = character at index5 (mirror 2)
- character at index0 = character at index6 (mirror 3)
Notice how again the two parts look like a sequence of 3 mirrors.
Problem
The problem states that we have to find the longest substring that is a palindrome in the string. A substring is a section of a string that consists of contiguous elements. Some examples are:
Input1: “BABAD” | Output1: “BAB” or “ABA”
Input2: “CBBD” | Output2: “BB”
Input3: “A” | Output3: “A”
Solutions
O(n²) Complexity
The simplest way to solve for this is to take every index as 1) a center 2) a Left Center and “expand outwards” to make character comparisons and find mirrors. The sequence with the maximum number of mirrors would be returned. Seems very simple and intuitive but the complexity is O(n²) because expanding a palindrome around a center could take O(n) time and we will explore every index in the string to be a center and left center, so O(n²) would be the time complexity.
O(n) Complexity
We can improve this runtime if we think of a way where we can leverage the previous palindromes found (as we navigate through the string) and reduce the “expanding outwards” part. Luckily, this is possible with “Manachar’s algorithm”.
Manachar’s algorithm
Before diving into the algorithm itself, we need to learn a few things first. For simplicity we will be focusing on Odd Pals for the most part. So let’s learn a few things in order:
1. Find mirror for an index around a center.
The distance between centerIndex (index of the center) and index should be equal to the distance between mirrorIndex (index of the mirror) and centerIndex:
centerIndex - index = mirrorIndex - centerIndexA little re-arranging gives us:
mirrorIndex = centerIndex + centerIndex - index
mirrorIndex = 2 * centerIndex - index2. Calculate mirrors around each center in a palindrome.
The mirrors row in the following illustration has the maximum number of mirrors around an index assuming it’s the center.
Lets look at the first 4 indexes to make the calculation logic more clear:
- index0: X has no mirrors since it has no characters on the left which could be mirrors.
- index1: Y has [index0/index2] as 1 mirror.
- index2: X has [index1/index3, index0/index4] as 2 mirrors.
- index3: Y has [index2/index4, index1/index5, index0/index6] as 3 mirrors.
- index4: X has [index3/index5, index2/index6, index1/index2, index0/index8] as 4 mirrors.
After the center for the longest palindrome, index4, notice how the mirror count is the same for as it’s mirror index:
- index5: MirrorIndex=2*4–5=index3 which has the same mirrors as 3.
- index6: MirrorIndex=2*4–6=index2 which has the same mirrors as 2.
- index7: MirrorIndex=2*4–7=index1 which has the same mirrors as 1.
- index8: MirrorIndex=2*4–8=index0 which has the same mirrors as 0.
The reason behind this is because it has already been established that index0 to index8 is a palindrome around a center index4 and hence the property of it reading same as forward and backwards ensure this equality.
3. Re-calculate mirrors with characters outside the palindrome.
Let’s add a new character outside one of the longest palindrome range to see how the mirror values are different from the values before.
The following illustration demonstrates the new mirror values where longest palindrome is at index 4(i am ignoring index5 with the same number for simplicity). The “right boundary” for center index4 is index8 and we have added “Y” at index9.
Lets look at the last 4 indexes to make the calculation logic more clear:
- index5: MirrorIndex has 3 mirrors but it has 4 mirrors because of an additional match of index1 and index9.
- index6: MirrorIndex has 2 mirrors but it has 3 mirrors because of an additional match of index3 and index9.
- index7: MirrorIndex has 2 mirrors but it has 3 mirrors because of an additional match of index5 and index9.
- index8: MirrorIndex has 1 mirror but it has 2 mirrors because of an additional match of index7 and index9.
This basically means that with more characters outside the palindrome, the mirrors will have to be recalculated for every index. Hence, it seems like each time we will have to expand outwards at every index(as described earlier) to figure out the right max, but instead of starting from the center index every time, can we use information that we know about the previous palindrome found to reduce the effort? Yes, we can.
4. Can we expand outwards with reduced effort?
To reduce effort, we need to find where to start the attempt to expand and for that we have to find the minimum mirrors that exist around that index as follows:
minimumMirrors = Min(rightBoundary-index, mirrors[mirrorIndex])The maximum count of mirrors from the mirror index that we can use for index is a count that stays inside the last found palindrome because if the count crosses the boundary of the palindrome then it is bringing in extra characters that we never checked with current index as center.
If it stays inside the boundary then we use the value as-is but if it’s outside the boundary, then it means that at-least the characters between mirrorIndex and the left boundary is palindromic with characters on the other side of the mirrorIndex. This is because the original mirror count is high enough to cross the boundary, so anything smaller should be a palindrome as well.
The count of this is actually the distance of the mirror index with the left boundary which is equal to the distance between the right boundary and index. Basically:
mirrorIndex — leftBoundary = rightBoundary - indexNow that we have a revised mirror count, we expand outwards from index+mirrors[index]+1 and index-mirrors[index]-1 to make character comparisons, rather than starting from the center.
5. Code
The code will now accommodate Even Pals as well by adding hashes in the input string as hypothetical centers.
/**** main function ****/
public String longestPalindrome(String s) {
if (s.length() < 2) {
return s;
}
// add hashes to String, example "abc" would become "#a#b#c#"
// this is because we need to find even pals as well. String hash = "#";
String hashedString = insertInto(s, hash);
int[] mirrors = new int[hashedString.length()];
int centerIndex = 0;
int rightBoundary = 0;
for (int index=1; index<hashedString.length(); index++) {
// find mirrorIndex.
int mirrorIndex = 2 * centerIndex - index;
// adjust number of mirrors.
if (index < rightBoundary) {
mirrors[index] = Math.min(rightBoundary - index;
mirrors[mirrorIndex]);
}
// expand outwards and make comparisons.
int leftIndex;
int rightIndex;
while((leftIndex = index - mirrors[index] - 1) >= 0
&& (rightIndex = index + mirrors[index] + 1)
< mirrors.length
&& hashedString.charAt(leftIndex)
== hashedString.charAt(rightIndex)) {
mirrors[index]++;
}
// adjust center and rightBoundary if the new palindrome
// found lies outside the boundary.
if (index + mirrors[index] > rightBoundary) {
centerIndex = index;
rightBoundary = centerIndex + mirrors[index];
}
}
int maxIndex = getIndexWithMaxMirrors(mirrors);
int maxMirrors = mirrors[maxIndex];
String maxString = hashedString
.substring(maxIndex - maxMirrors,
maxMirrors + maxIndex + 1)
.replace(hash,"");
return maxString;
}/**** private helpers ****/
private int getIndexWithMaxMirrors(int[] mirrors) {
int maxValue = -1;
int maxIndex = -1;
for (int index=0; index<mirrors.length; index++) {
if (mirrors[index] <= maxValue) {
continue;
}
maxValue = mirrors[index];
maxIndex = index;
}
return maxIndex;
}
private String insertInto(String s, String marker) {
StringBuilder sb = new StringBuilder();
for (char ch: s.toCharArray()) {
sb.append(marker);
sb.append(ch);
}
sb.append(marker);
return sb.toString();
}
6. Wait — how is the complexity O(N)?
The rightBoundary always moves to the right and at max will take N steps. Plus you never repeat a step and don’t start from the center but leverage on already found palindromes and mirror calculations.
If you found this article useful, please help me reach more dev learners!
Show some ❤ by giving “claps” 👏 at the left margin of the page (on desktop) or at the bottom (on mobile). You can do so up to 50 times by clicking continuously!
Anum Malik
Follow NMTechBytes on Twitter for my daily tech bites :)
Special Thanks
[1] Longest Palindromic Substring O(N) Manacher’s Algorithm:
https://www.youtube.com/watch?v=nbTSfrEfo6M
[2] Manacher’s Algorithm: https://www.hackerrank.com/topics/manachers-algorithm
[3] How do I analyze the time complexity of Manacher’s algorithm?:https://www.quora.com/How-do-I-analyze-the-time-complexity-of-Manachers-algorithm
