Longest Palindromic Substring

1. Generate substrings of the given string such that substring having greater length will be generated first.
2. To do this, run a loop where iterator len will go from N to 1, where N is the length of the given string.
3. Run a nested loop and fix an iterator j that will point at the starting index of the substring.
4. Get the substring from j to j+len.
5. If the substring is a palindrome, return the substring (As the substring will be of the longest length and minimum starting index).

1. If the string length is less than or equal to 1 then return the string, as one length string is always palindromic.
2. Initialize a DP array of data type boolean, DP[i][j] will store false if INPUT[i,j] is not palindromic otherwise it will store true.
3. Store all the diagonal elements (DP[i][i]) as true, as INPUT[i,i] will always be palindromic.
4. For substring of length 2, check if INPUT[i] is equal to INPUT[i+1] then store DP[i][i+1] as true.
5. Run a loop for length of substring greater than 2, fill the DP array diagonally, To calculate DP[i][j], check the value of DP[i+1][j-1], if the value is true and INPUT[i] is same as INPUT[j], then we make DP[i][j] true otherwise false.
6. For every DP[i][j] true, update the length and starting index of the substring.
7. Return the substring of the string having starting index as start and of maximum length.

1. If the string length is less than or equal to 1 then return the string, as a single character is always palindromic.
2. The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
3. To generate odd length palindrome, run a loop where i will be between 0 to N-1, Fix centre i, and expand in both directions for longer palindromes, odd length palindromes will have a character at the centre.
4. Similarly, for even length palindrome, fix the centre as i, i+1, and expand in both directions, even palindrome will have partition between ith char and i+1th char as the centre.
5. If the length of the current palindromic substring length is greater than update the starting length of the string and length of the palindromic substring.
6. Return the substring of the string having starting index as start and of maximum length.

For expanding :

1. For expanding around a center i for odd length, initialize two variables left and right to i and go until LEFT and RIGHT are in range and INPUT[LEFT] == INPUT[RIGHT]. Decrement the LEFT and increment the RIGHT.
2. For expanding around a centre i and i+1 for even length, initialise two variables LEFT = i and RIGHT = i+1, and go until LEFT and RIGHT are in range and INPUT[LEFT] == INPUT[RIGHT]. Decrement the LEFT and increment the RIGHT.
3. Return the length of the palindromic substring.

Manacher’s algorithm optimizes our solution by using some insights into how palindromes work.

Let C be the center of the longest length palindrome we have encountered till now. And let L and R be the left and right boundaries of this palindrome, i.e., the left-most character index and the right-most character index respectively.

Take an example: STR = “abacabacabb”

When going from left to right, when i is at index 1, the longest palindromic substring is “aba” (length = 3).

The longest palindromic substring for the given string is 9 when the palindrome is centered at index 5:

CURR_L: For any palindrome centered at a center C the CURR_L of the mirror of the given index j in left direction, the mirror of index j is j’ such that

J’ = 2*C - J

For palindrome “abacaba”, the mirror of j is j’ and the mirror of j’ is j.

for some j, its mirror j’ for palindrome “abacaba”

We try to “expand” the palindrome at each i (CURR_R). When I say the word expand, it means that I’ll check whether there exists a palindrome centered at i and if there exists one, I’ll store the “expansion length” to the left or to the right in a new array called LEN_ARR[] or P[] array. If the palindrome at i expands beyond the current right boundary r, then c is updated to i and new l, r are found and updated.

Let’s take the previously discussed palindrome “abacaba” which is centered at i = 3.

P[i] = 3 as expansion length for palindrome centered at i is 3

Hence, the LEN_ARR[] or P[] array stores the expansion length of the palindrome centered at each index. But we don’t need to manually go to each index and expand to check the expansion length every time. This is exactly where Manacher’s algorithm optimizes better than brute force, by using some insights on how palindromes work. Let’s see how the optimization is done.

Let’s see the P[] array for the string “abacaba”.

When i = 4, the index is inside the scope of the current longest palindrome, i.e., i < r. So, instead of naively expanding at i, we want to know the minimum expansion length that is certainly possible at i, so that we can expand on that minimum P[i] and see, instead of doing from start. So, we check for mirror i’. As long as the palindrome at index i’ does NOT expand beyond the left boundary (l) of the current longest palindrome, we can say that the minimum certainly possible expansion length at i is P[i’].

Here we are only talking about the minimum possible expansion length, the actual expansion length could be more and, we’ll find that out by expanding later on. In this case, P[4] = P[2] = 0. We try to expand but still, P[4] remains 0.

Now, if the palindrome at index i’ expands beyond the left boundary (l) of the current longest palindrome, we can say that the minimum certainly possible expansion length at i is r-i.

For example: STR = “acacacb”

In the above diagram, palindrome centered at i’ expands beyond the left boundary

So, P[4] = 5–4 = 1

Keep Updating P[i] to the minimum certainly possible expansion length. Now the only thing left is to expand at i after P[i], so we check characters from index (P[i] + 1) and keep expanding at i.

If this palindrome expands beyond r, update c to i and r to (i + P[i]). The P[] or LEN_ARR[] array is now filled and the maximum value in this array gives us the longest palindromic substring in the given string.