Make delicious recipes!

O(n) method to find longest palindrome in a string



Problem: Given a string s, find the longest palindrome in that string.

Examples:

S = "cabba", Output = "abba"

S = "abcbade", Output = "abcba"

S = "ababacababa", Output = "ababacababa"


Solution: A naive solution to the problem is:
  1. Loop over all the chars in the string.
  2. At each index, check if there is a palindrome by comparing left and right chars.
  3. Since we may have to potentially compare all the chars at each index, order is O(n2)

Note that order is O(n2) only when there are multiple palindromes.

When there is only one palindrome, then order remains O(n) only.
(because at every index, the left-right comparison breaks in the first comparison for all indices except where the actual palindrome is)

Key to making this algorithm O(n) is to gather some information from previous palindrom when moving to the next index.

Lets take the string "ababa".

Lets also create an array int palindromLengths[] such that palindromLengths[i] stores the length of the palindrome centered at i.

For the above string, the palindromLengths would be:
ababa
01210 (We are storing the length of half the palindrome only. It will simplify things later)

From the above, we can find a very interesting property of a palindrome.
If there is a mini-palindrome in one half of a palindrome, then the second half of the palindrome would also have that palindrome.

So if we have filled palindromLengths[] till the center of any palindrome, we can know about palindromes in the right half of that palindrome immediately.
For example:
In the following string:
d a b a c a b a c a b
The palindromLengths would begin forming as:
0 0 1 0 3 0
Before moving to next char 'b', we can see that its containing palindrome 'abacaba' had a mini palindrome 'aba' centered at
a similar position 'b' mirrored around 'c'
Since the parent palindrome is a palindrome anyway, we immediately know that palindromLengths value for this 'b' has to be
same as that of the mirror position.
Let's continue further.

0 0 1 0 3 0 1

Wait!
Can we just put an exact same value here as the value at the mirror index?
Not that the length of the string before the parent palindrom 'abacaba' is not the same as that after it.
So the mirrored value gives only the minimum length of the palindrome.
We will use the minimum value to avoid duplicate comparison and start comparing left-right again assuming a mini-palindrome.
Thus, we do find a bigger palindrome at this 'b' and we update the palindromLengths as:
0 0 1 0 3 0 4

Moving on to next char 'a', we see that it had a palindromLengths value of 0 in the parent palindrome 'bacabacab' (note
that the parent palindrome for this 'a' is not 'abacaba' because this 'a' does not fall under it.)
We go ahead and compute the full palindromLengths for all the remaining characters.
0 0 1 0 3 0 4 0 3 0 1

The longest palindrom is thus located where the value of palindromLengths is maximum and that would be 'bacabacab'

From the above analysis, we find one property which helps to reduce the O(n2) to O(n):

If there is a parent palindrome enveloping the current character, then we can find the minimum length of the palindrome with center at the current index by looking at the mirror position in palindromLengths.

Also, note that we have considered only odd-length palindromes in the above.
For even length palindromes like "abba", the center lies in between two characters and it becomes difficult to apply the above.
This can be simplified by adding a '#' after each character. This converts "abba" to "#a#b#b#a#".
With this technique, any input string becomes 2n+1 in length which is guaranteed to be odd and which also converts every even palindrome into an odd palindrome.

With this analysis, we are now in a position to write the following code:
public class LongestPalindrome
{
    public static void main(String[] args)
    {
        //System.out.println(longestPalindrome("abcdcb"));
        //System.out.println(longestPalindrome("cdababcbabae"));
        System.out.println(longestPalindrome("ababacababa"));
    }

    /**
     * Adds a # after each character of input string.
     * Also adds a ^ at the beginning and a $ at the end.
     * For example, S = "abba", T = "^#a#b#b#a#$".
     * ^ and $ signs help to avoid bounds checking and terminate the
     * while loop checking left and right of 'i' in longestPalindrome()
     */
    static String preProcess(String s) {
        int n = s.length();
        if (n == 0) return "^$";
        String ret = "^";
        for (int i = 0; i < n; i++)
            ret += "#" + s.substring(i, i+1);

        ret += "#$";
        return ret;
    }

    /**
     * Finds the longest palindrome in given string
     */
    static String longestPalindrome(String s)
    {
        String T = preProcess(s);
        System.out.println(T);
        int n = T.length();
        int palindromLengths[] = new int[n];
        int prevPalindromCenter = 0;
        int prevPalindromEnd = 0;

        for (int i = 1; i < n-1; i++)
        {
            int i_mirror = prevPalindromCenter - (i - prevPalindromCenter);

            palindromLengths[i] =
                    (prevPalindromEnd > i) ?
                    Math.min (prevPalindromEnd-i, palindromLengths[i_mirror])
                    : 0;
            debugVars(palindromLengths, prevPalindromCenter, prevPalindromEnd, i, i_mirror);

            // Check how big is the current palindrome, centered at i
            while (T.charAt(i + 1 + palindromLengths[i]) == T.charAt(i - 1 - palindromLengths[i]))
                palindromLengths[i]++;
            debug(T, palindromLengths, i);

            // If prevPalindrom is no longer reaching till i,
            // reset the prev palindrom's center and end
            if (i + palindromLengths[i] > prevPalindromEnd)
            {
                prevPalindromCenter = i;
                prevPalindromEnd = i + palindromLengths[i];
            }
            debugVars(palindromLengths, prevPalindromCenter, prevPalindromEnd, i, i_mirror);
            System.out.println("\n");
        }

        return findMaxInArray(s, n, palindromLengths);
    }

    /**
     * Just finds the max. value in an array
     * Largest palindrome is centered at the char with that max. value
     */
    static String findMaxInArray(String s, int n, int[] P)
    {
        int maxLen = 0;
        int centerIndex = 0;

        for (int i = 1; i < n-1; i++)
        {
            if (P[i] > maxLen)
            {
                maxLen = P[i];
                centerIndex = i;
            }
        }

        int startIndex = (centerIndex - 1 - maxLen)/2;
        return s.substring(startIndex, startIndex + maxLen);
    }

    static void debugVars(
            int[] palindromLengths, int prevPalindromCenter,
            int prevPalindromEnd, int i, int i_mirror)
    {
        System.out.println("\ni=" + i + ", prevPalindromCenter=" + prevPalindromCenter +
                ", i_mirror=" + i_mirror + ", prevPalindromEnd=" + prevPalindromEnd +
                ", P[" + i + "]=" + palindromLengths[i]);
    }

    static void debug(String T, int[] palindromLengths, int i)
    {
        System.out.println(T);
        for (int j=0;j<i;j++)
            System.out.print(" ");
        System.out.println("^");
        for (int j=0;j<=i;j++)
            System.out.print(palindromLengths[j]);
        System.out.println();
    }
}

Note that a normal O(n2) algorithm is very similar to this solution too.

Only difference between these two algorithms are:
  1. Lines 44-47 (absent in O(n2))
    So (O(n2) initializes palindromLengths[i] to 0 always)
  2. Lines 55-61 (absent in O(n2))

Sample Execution
Input: ababacababa
^#a#b#a#b#a#c#a#b#a#b#a#$

i=1, prevPalindromCenter=0, i_mirror=-1, prevPalindromEnd=0, P[1]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
 ^
00

i=1, prevPalindromCenter=1, i_mirror=-1, prevPalindromEnd=1, P[1]=0



i=2, prevPalindromCenter=1, i_mirror=0, prevPalindromEnd=1, P[2]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
  ^
001

i=2, prevPalindromCenter=2, i_mirror=0, prevPalindromEnd=3, P[2]=1



i=3, prevPalindromCenter=2, i_mirror=1, prevPalindromEnd=3, P[3]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
   ^
0010

i=3, prevPalindromCenter=2, i_mirror=1, prevPalindromEnd=3, P[3]=0



i=4, prevPalindromCenter=2, i_mirror=0, prevPalindromEnd=3, P[4]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
    ^
00103

i=4, prevPalindromCenter=4, i_mirror=0, prevPalindromEnd=7, P[4]=3



i=5, prevPalindromCenter=4, i_mirror=3, prevPalindromEnd=7, P[5]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
     ^
001030

i=5, prevPalindromCenter=4, i_mirror=3, prevPalindromEnd=7, P[5]=0



i=6, prevPalindromCenter=4, i_mirror=2, prevPalindromEnd=7, P[6]=1
^#a#b#a#b#a#c#a#b#a#b#a#$
      ^
0010305

i=6, prevPalindromCenter=6, i_mirror=2, prevPalindromEnd=11, P[6]=5



i=7, prevPalindromCenter=6, i_mirror=5, prevPalindromEnd=11, P[7]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
       ^
00103050

i=7, prevPalindromCenter=6, i_mirror=5, prevPalindromEnd=11, P[7]=0



i=8, prevPalindromCenter=6, i_mirror=4, prevPalindromEnd=11, P[8]=3
^#a#b#a#b#a#c#a#b#a#b#a#$
        ^
001030503

i=8, prevPalindromCenter=6, i_mirror=4, prevPalindromEnd=11, P[8]=3



i=9, prevPalindromCenter=6, i_mirror=3, prevPalindromEnd=11, P[9]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
         ^
0010305030

i=9, prevPalindromCenter=6, i_mirror=3, prevPalindromEnd=11, P[9]=0



i=10, prevPalindromCenter=6, i_mirror=2, prevPalindromEnd=11, P[10]=1
^#a#b#a#b#a#c#a#b#a#b#a#$
          ^
00103050301

i=10, prevPalindromCenter=6, i_mirror=2, prevPalindromEnd=11, P[10]=1



i=11, prevPalindromCenter=6, i_mirror=1, prevPalindromEnd=11, P[11]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
           ^
001030503010

i=11, prevPalindromCenter=6, i_mirror=1, prevPalindromEnd=11, P[11]=0



i=12, prevPalindromCenter=6, i_mirror=0, prevPalindromEnd=11, P[12]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
            ^
00103050301011

i=12, prevPalindromCenter=12, i_mirror=0, prevPalindromEnd=23, P[12]=11



i=13, prevPalindromCenter=12, i_mirror=11, prevPalindromEnd=23, P[13]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
             ^
001030503010110

i=13, prevPalindromCenter=12, i_mirror=11, prevPalindromEnd=23, P[13]=0



i=14, prevPalindromCenter=12, i_mirror=10, prevPalindromEnd=23, P[14]=1
^#a#b#a#b#a#c#a#b#a#b#a#$
              ^
0010305030101101

i=14, prevPalindromCenter=12, i_mirror=10, prevPalindromEnd=23, P[14]=1



i=15, prevPalindromCenter=12, i_mirror=9, prevPalindromEnd=23, P[15]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
               ^
00103050301011010

i=15, prevPalindromCenter=12, i_mirror=9, prevPalindromEnd=23, P[15]=0



i=16, prevPalindromCenter=12, i_mirror=8, prevPalindromEnd=23, P[16]=3
^#a#b#a#b#a#c#a#b#a#b#a#$
                ^
001030503010110103

i=16, prevPalindromCenter=12, i_mirror=8, prevPalindromEnd=23, P[16]=3



i=17, prevPalindromCenter=12, i_mirror=7, prevPalindromEnd=23, P[17]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
                 ^
0010305030101101030

i=17, prevPalindromCenter=12, i_mirror=7, prevPalindromEnd=23, P[17]=0



i=18, prevPalindromCenter=12, i_mirror=6, prevPalindromEnd=23, P[18]=5
^#a#b#a#b#a#c#a#b#a#b#a#$
                  ^
00103050301011010305

i=18, prevPalindromCenter=12, i_mirror=6, prevPalindromEnd=23, P[18]=5



i=19, prevPalindromCenter=12, i_mirror=5, prevPalindromEnd=23, P[19]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
                   ^
001030503010110103050

i=19, prevPalindromCenter=12, i_mirror=5, prevPalindromEnd=23, P[19]=0



i=20, prevPalindromCenter=12, i_mirror=4, prevPalindromEnd=23, P[20]=3
^#a#b#a#b#a#c#a#b#a#b#a#$
                    ^
0010305030101101030503

i=20, prevPalindromCenter=12, i_mirror=4, prevPalindromEnd=23, P[20]=3



i=21, prevPalindromCenter=12, i_mirror=3, prevPalindromEnd=23, P[21]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
                     ^
00103050301011010305030

i=21, prevPalindromCenter=12, i_mirror=3, prevPalindromEnd=23, P[21]=0



i=22, prevPalindromCenter=12, i_mirror=2, prevPalindromEnd=23, P[22]=1
^#a#b#a#b#a#c#a#b#a#b#a#$
                      ^
001030503010110103050301

i=22, prevPalindromCenter=12, i_mirror=2, prevPalindromEnd=23, P[22]=1



i=23, prevPalindromCenter=12, i_mirror=1, prevPalindromEnd=23, P[23]=0
^#a#b#a#b#a#c#a#b#a#b#a#$
                       ^
0010305030101101030503010

i=23, prevPalindromCenter=12, i_mirror=1, prevPalindromEnd=23, P[23]=0


ababacababa


Here is a comparison of the logs between O(n2) and O(n)


Note how the O(n) solution gets an advantage by beginning at already known mini-palindrome length.

Reference: Manacher's Algorithm





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal