Manacher's Algorithm - Linear Time Solution for Longest Palindrome Problem

While solving some leetcode problems. I came across problem #5, which is to find the longest palindrome substring of a string.

A palindrome is a string that reads the same forward and backward. e.g. racecar, madam. So given a string abcacbbc, the longest palindrome substring in the case will be bcacb.

There are several ways to solve this, but they come with different time and space complexities. Here are the most common solutions:

1. Brute-force
2. Dynamic programming
3. Expand from centers
4. Manacher's algorithm

The brute-force approach has a time and space complexity of $O(n^3),$ $O(n)$ respectively. While the Dynamic programming approach has a time and space complexity of $O(n^2).$

My two favorites out of the four are Manacher's algorithm and the expand-from-centers approach.

The Expand from centers approach is the most intuitive in my opinion and it has a time complexity of $O(n^2),$ and a space complexity of $O(1).$ It is a good stepping stone for understanding Manacher's algorithm.

The Manacher's algorithm, on the other hand, is a little more difficult but has a time and space complexity of $O(n)$ and it's most optimal solution there is for now, although I don't think there exists a solution in $O(\log \; n)$ or in constant time, since each character in the string needs to be examined (but anything is possible, right?).

I will showcase both the expanding and the Manacher's approach in this post but I will emphasize more on Manacher's algorithm.

Expand from centers approach

In this approach, we consider the length of the palindrome.

A palindrome can be of even length or odd length.

If the palindrome is even, it will have two-like characters at its center eg. ac'bb'ca.
While that of odd length will have a center character and its sides mirror each other eg. ac'b'ca.

So, as we iterate through each character of the string. We test for even and odd palindromes with the character as its center. At the end of the palindrome, we check if the length of the palindrome is bigger than the last biggest palindrome recorded and update if it is.

The expand-from-centers method is illustrated in the diagram below. We iterated through each character with $i,$ as its index and text for even and odd palindromes.

We traverse through the characters of the string abcacbbc, testing for even palindromes (arrows at the bottom) and odd (palindromes) while keeping track of the best left and best right indices. When a palindrome reaches its end, we compare the distance of its left and right with the best recorded left and right and update if it's bigger, before moving to the next character. If no palindrome can be made from both the odd and even perspective, no comparison is made.

After traversing, we take the substring starting from the best left to the best right (inclusive) as our longest palindrome.

Manacher's Algorithm

This is the major part of this article. I will explain, each step of the algorithm in detail with illustrations, and I will give a Rust lang implementation of the algorithm at the end. For exercise, you can try converting to your primary language using both the illustration and code as guidance.

Here we need to keep track of some important variables, which are:

1. i - This is the index of the character at the current iteration.
2. center - This is the index of the center of the outermost palindrome.
3. right - This is the index of the right side of the outermost palindrome.
4. p - This is the array that stores the length of a side of the palindrome centered at each character of the string.

Steps for using the Manacher's algorithm to find the longest palindrome substring of abcacbbc

In the following steps, I will demonstrate Manacher's algorithm by finding the longest palindrome substring of abcacbbc.

Step 1: Adding Separators

Recall that when using the expand from centers method, since even palindromes do not have a unique center, we took both odd and even cases into consideration. To skip the case of even and odd palindromes, we can modify the string by inserting a separator # in between each character before finding the palindrome substring.

When the string is modified in this manner, we can get a center of the palindrome for both even and odd lengths. If we have a palindrome of even lengths, such as ceec, when modified the string becomes #c#e#e#c#, the modified string has an odd length, and has the fifth character # as its center. For that of odd, if we have a palindrome as bcacb, after modifying the string, we have #b#c#a#c#b# and the character a as the center of the palindrome.

So given the string abcacbbc, we modify it to #a#b#c#a#c#b#b#c#.

Step 2: Initialize variables

The primary variables for the algorithm are i, center, right, and p. You can keep a variable max_p for the maximum number in the array p and max_p_index for its index.

After adding the separator in between each character the resulting string will have a length of $2n + 1,$ where n is the length of the original string.

The array p keeps track of the length of the sides of each palindrome p[i] centered at the character with index i in the modified string. Initialize p as an array of length $2n + 1$ and fill with the number 0.

p : [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

The traversal will start at index 2 i = 2 since the palindrome centered at the first two characters (index 0 & 1) can be determined.

By examining the string #a#b#c#a#c#b#b#c#, we can see that at index 1, the character a is the center of the palindrome #a#. The palindrome substring #a# has 1 character at each side of its center a, therefore we update p to contain 1 at index 1. p[1] = 1. Set variables center = 1 and right = 2.

The variables are initialized as follows:

org_string: abcacbbc
mod_string: #a#b#c#a#c#b#b#c#
p: [0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
i: 2
center: 1
right: 2
max_p: 1 //maximum number in p
max_p_index: 1 //index of the maximum number in p

The diagram below illustrates the string and the array p. The center is marked as the dotted line, the right is marked with R and the current character being examined is marked with the red line.

Step 3: The Travesal

In this step, we perform the algorithm for checking palindromes. In Manacher's algorithm, the steps used for checking palindromes in the expand-from-centers method are reduced using mirroring.

Mirroring is a method of avoiding character checks when testing a character within an already discovered palindrome (which we refer to as the super palindrome), by calculating the minimum of the calculated size of the palindrome centered at its mirror and the right of the super palindrome. This is best illustrated using examples.

We'll go over the string's characters one by one. Every time we iterate, we carry out the subsequent procedures:

1. Apply mirroring if it's within a super palindrome.
2. Check for palindromes centered at the character or the mirrored portion, if mirroring was applied.
3. Update the center and right if a palindrome was found.

We shall demonstrate these procedures with the illustrations below.

At index 2, since # is at the boundary of the palindrome #A#, mirroring won't be applied (It needs to be within the palindrome). Following that, we check if the character is the center of a palindrome. However, because a!= b, there is no palindrome centered at #, therefore proceed to the next character.

At index 3, B is outside the last palindrome #A#, therefore mirroring won't be applied. We then check if the character is the center of a palindrome.

From B, we only need to move one step outwards to get to the end of its palindrome, therefore we have a palindrome #B# centered at B. And we update p[3] = 1.

Since we have found a palindrome at index 3, we update center = 3 and right = 4 (The index of the right end of the palindrome) and move to the next character.

At index 4, since # is at the boundary of the palindrome #B#, mirroring won't be applied. Following that, we check if the character is the center of a palindrome. However, because b!= c, there is no palindrome centered at #, therefore proceed to the next character.

At index 5, C is outside the last palindrome #B#, therefore mirroring won't be applied. We then check if the character is the center of a palindrome.

From C, we only need to move one step outwards to get to the end of its palindrome, therefore we have a palindrome #C# centered at C. And we update p[5] = 1.

Since we have found a palindrome at index 5, we update center = 5 and right = 6 (The index of the right end of the palindrome) and move to the next character.

At index 6, since # is at the boundary of the palindrome #C#, mirroring won't be applied. Following that, we check if the character is the center of a palindrome. However, because c!= a, there is no palindrome centered at #, therefore proceed to the next character.

At index 7, A is outside the last palindrome #C#, therefore mirroring won't be applied. We then check if the character is the center of a palindrome.

From A, if we move 5 steps outwards, we get to the end of its palindrome, therefore we have a palindrome #B#C#A#C#B# centered at A. And we update p[7] = 5.

Since we have found a palindrome at index 5, we update center = 7 and right = 12 (The index of the right end of the palindrome) and move to the next character.

At index 8, since # is within the last palindrome #B#C#A#C#B#, we apply mirroring. Considering the center of the last palindrome A, the mirror of # at index 8 is # at index 6. Therefore we update p[8] = min(p[6], right - 8). That is the minimum between the size of its mirror p[6] and the distance between the right of the super palindrome and index 8 right - 8. Since p[6] = 0, we update p[8] = min(0, 12 - 8) = min(0, 4) = 0.

The formula for obtaining the mirror of a character at index i is 2 * center - i.

Following that, we check if there is a palindrome centered around the mirrored portion #. However, because a!= c, there is no palindrome centered at #, therefore proceed to the next character.

At index 9, since C is within the last palindrome #B#C#A#C#B#, we apply mirroring. Considering the center of the last palindrome A, the mirror of C at index 9 is C at index 5 (2 * center - 9). Therefore we update p[9] = min(p[5], right - 9) = min(1, 12 - 9) = min(1, 3) = 1.

Therefore our mirrored portion is the area one step outwards of C.

Following that, we check if there is a palindrome centered around the mirrored portion #C#. However, because a!= b, there is no palindrome centered at #C#, therefore proceed to the next character.

At index 10, since # is within the last palindrome #B#C#A#C#B#, we apply mirroring. Considering the center of the last palindrome A, the mirror of # at index 10 is # at index 4 (2 * center - 10). Therefore we update p[10] = min(p[4], right - 10) = min(0, 12 - 10) = min(0, 2) = 0.

Following that, we check if there is a palindrome centered around the mirrored portion #. However, because c!= b, there is no palindrome centered at #, therefore proceed to the next character.

At index 11, since B is within the last palindrome #B#C#A#C#B#, we apply mirroring. Considering the center of the last palindrome A, the mirror of B at index 11 is B at index 3 (2 * center - 11). Therefore we update p[11] = min(p[3], right - 11) = min(1, 12 - 11) = min(1, 1) = 1.

Therefore our mirrored portion is the area one step outwards of B.

Following that, we check if there is a palindrome centered around the mirrored portion #B#. However, because c!= b, there is no palindrome centered at #B#, therefore proceed to the next character.

At index 12, # is at the boundary of the last palindrome, therefore mirroring won't be applied. We then check if the character is the center of a palindrome.

From #, if we move 4 steps outwards, we get to the end of its palindrome, therefore we have a palindrome #C#B#B#C# centered at #. And we update p[12] = 4.

Since we have found a palindrome at index 12, we update center = 12 and right = 16 (The index of the right end of the palindrome) and move to the next character.

At index 13, since B is within the last palindrome #C#B#B#C#, we apply mirroring. Considering the center of the last palindrome #, the mirror of B at index 13 is B at index 11 (2 * center - 13). Therefore we update p[13] = min(p[11], right - 13) = min(1, 16 - 13) = min(1, 3) = 1.

Therefore our mirrored portion is the area one step outwards of B.

Following that, we check if there is a palindrome centered around the mirrored portion #B#. However, because b != c, there is no palindrome centered at #B#, therefore proceed to the next character.

At index 14, since # is within the last palindrome, we apply mirroring. Considering the center of the last palindrome #, the mirror of # at index 14 is # at index 10 (2 * center - 14). Therefore we update p[14] = min(p[10], right - 14) = min(0, 16 - 14) = min(0, 2) = 0.

Following that, we check if there is a palindrome centered around the mirrored portion #. However, because b!= c, there is no palindrome centered at #, therefore proceed to the next character.

At index 15, since C is within the last palindrome, we apply mirroring. Considering the center of the last palindrome #, the mirror of C at index 15 is C at index 9 (2 * center - 15). Therefore we update p[15] = min(p[9], right - 15) = min(1, 16 - 15) = min(1, 1) = 1.

Therefore our mirrored portion is the area one step outwards of C.

Following that, we check if there is a palindrome centered around the mirrored portion #C#. But since we are at the end of the string, we end the iteration.

Step 4: Slice the Substring and Remove the Separators

During the iteration, you will need to keep track of the index of the maximum element of the array p. In our case, the maximum element is at index 7 and p[7] = 5.

Therefore we take the slice of the string starting from index 2 = 7 - 5 to index 12 = 7 + 5 including the last index. Hence our substring is #B#C#A#C#B#.

Finally, we filter out the separators # and we get our longest palindrome substring as BCACB

Thanks for reading. If you found this helpful, please support by liking and sharing with your friends and colleagues. This took me a lot of time to prepare. Thanks once more.

You can contact me via email at augustinemadu9@gmail.com. Follow me on X @CudiLala_.

Here is the Rust lang implementation of Manacher's algorithm.

pub fn longest_palindrome(s: String) -> String {
  //modify string by adding separators
  let s: Vec<u8> = s
    .bytes()
    .flat_map(|b| [b'#', b])
    .chain("#".bytes())
    .collect();

  let n = s.len();

  let mut p = vec![0; n];

  p[1] = 1;

  let mut i = 2;
  let mut center = 1;
  let mut right = 2;
  let mut max_p = 1;
  let mut max_p_index = 1;

  while i < n {
    //if the character is within the last palindrome
    if i < right {
      //mirroring

      //index of the mirror of the current character
      let i_mirror = 2 * center - i;

      //minimum of between the size of its mirror and the distance to the right
      p[i] = p[i_mirror].min(right - i);
    }

    //test for palindrome centered around the character or mirrored portion
    while i - p[i] > 0 && i + p[i] + 1 < n && s[i - p[i] - 1] == s[i + p[i] + 1] {
      p[i] += 1
    }

    //update center and right if palindrome is found
    if i + p[1] > right {
      center = i;
      right = i + p[i];
    }

    //update if the palindrome centered at the current character is bigger
    if p[i] > max_p {
      max_p = p[i];
      max_p_index = i;
    }
    i += 1;
  }

  //select substring and remove separators
  s.into_iter()
    .skip(max_p_index - max_p + 1)
    .take(2 * max_p - 1)
    .filter(|u| *u != b'#')
    .map(|u| u as char)
    .collect()
}

Have a nice day!