Longest Palindromic Substring With Manachar’s Algorithm

NMTechBytes
Jul 26, 2020 · 7 min read

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:

A little re-arranging gives us:

2. 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:

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:

Now 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.

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

The Startup

Get smarter at building your thing. Join The Startup’s +724K followers.

NMTechBytes

Written by

Anum Sarmad Malik | Software Engineer @ Apple Siri | twitter.com/anumsarmadmalik | dev.to/anumsmalik

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +724K followers.

NMTechBytes

Written by

Anum Sarmad Malik | Software Engineer @ Apple Siri | twitter.com/anumsarmadmalik | dev.to/anumsmalik

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +724K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store