Longest Palindromic Substring : From simple to complex solutions

Problem Description
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Solution
I. Simple solution with expansion from an Index

For each index, we can try to expand as much as possible so that the substring is still palindromic. However, this is O(N^2) time complexity.

public class Solution {
    public String longestPalindrome(String s) {
        if(s.length() <= 1) return s;
        int start = 0, maxLength = 1;
        for(int i = 0; i<s.length();){
            if(s.length() - i <= maxLength/2) break;
            int j = i, k = i;
            while(k < s.length() - 1 && s.charAt(k+1) == s.charAt(k)) ++k;
            i = k + 1;
            while(k < s.length() - 1 && j > 0 && s.charAt(k+1) == s.charAt(j-1)) {++k; --j; }
            int l = k-j+1;
            if(l > maxLength) {maxLength = l; start = j;}
        }
        return s.substring(start, start + maxLength);
    }
}

II. Manacher Algorithm in Linear time

If you are not familiar with Manacher algorithm, you can read more on this wiki article .

import java.util.Arrays;

public class Solution {
    
    public static String longestPalindrome(String s) {
        if (s==null || s.length()==0)
            return "";
        
        char[] s2 = addBoundaries(s.toCharArray());
        int[] p = new int[s2.length]; 
        int c = 0, r = 0; // Here the first element in s2 has been processed.
        int m = 0, n = 0; // The walking indices to compare if two elements are the same
        for (int i = 1; i<s2.length; i++) {
            if (i>r) {
                p[i] = 0; m = i-1; n = i+1;
            } else {
                int i2 = c*2-i;
                if (p[i2]<(r-i)) {
                    p[i] = p[i2];
                    m = -1; // This signals bypassing the while loop below. 
                } else {
                    p[i] = r-i;
                    n = r+1; m = i*2-n;
                }
            }
            while (m>=0 && n<s2.length && s2[m]==s2[n]) {
                p[i]++; m--; n++;
            }
            if ((i+p[i])>r) {
                c = i; r = i+p[i];
            }
        }
        int len = 0; c = 0;
        for (int i = 1; i<s2.length; i++) {
            if (len<p[i]) {
                len = p[i]; c = i;
            }
        }
        char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
        return String.valueOf(removeBoundaries(ss));
    }
 
    private static char[] addBoundaries(char[] cs) {
        if (cs==null || cs.length==0)
            return "||".toCharArray();

        char[] cs2 = new char[cs.length*2+1];
        for (int i = 0; i<(cs2.length-1); i = i+2) {
            cs2[i] = '|';
            cs2[i+1] = cs[i/2];
        }
        cs2[cs2.length-1] = '|';
        return cs2;
    }

    private static char[] removeBoundaries(char[] cs) {
        if (cs==null || cs.length<3)
            return "".toCharArray();

        char[] cs2 = new char[(cs.length-1)/2];
        for (int i = 0; i<cs2.length; i++) {
            cs2[i] = cs[i*2+1];
        }
        return cs2;
    }    
}

III. Gusfield's Algorithm

This is an algorithm by Gusfield. If you want to learn more about string algorithm, take a look at Gusfield's course here.

public class Solution {
    char[] temp; 
    public int match(int a, int b,int len){ 
        int i = 0; 
        while (a-i>=0 && b+i<len && temp[a-i] == temp[b+i]) i++; 
        return i; 
    }
    
    public String longestPalindrome(String s) {
        
        //This makes use of the assumption that the string has not more than 1000 characters.
        temp=new char[1001*2];
        int[] z=new int[1001 * 2];
        int L=0, R=0;
        int len=s.length();
    
        for(int i=0;i<len*2+1;i++){
            temp[i]='.';
        }
    
        for(int i=0;i<len;++i){
            temp[i*2+1] = s.charAt(i);
        }
    
        z[0]=1;
        len=len*2+1;
    
        for(int i=0;i<len;i++){
            int ii = L - (i - L);   
            int n = R + 1 - i;
            if (i > R)
            {
                z[i] = match(i, i,len);
                L = i;
                R = i + z[i] - 1;
            }
            else if (z[ii] == n)
            {
                z[i] = n + match(i-n, i+n,len);
                L = i;
                R = i + z[i] - 1;
            }
            else
            {
                z[i] = (z[ii]<= n)? z[ii]:n;
            } 
        }
    
        int n = 0, p = 0;
        for (int i=0; i<len; ++i)
            if (z[i] > n)
                n = z[p = i];
    
        StringBuilder result=new StringBuilder();
        for (int i=p-z[p]+1; i<=p+z[p]-1; ++i)
            if(temp[i]!='.')
                result.append(String.valueOf(temp[i]));
    
        return result.toString();
    }
}

Shortest Palindrome and KMP algorithm: A little thought!

In leetcode, Shortest Palindrome is one of the site's interesting algorithmic problems. It states that from a string s find the shortest palindrome by adding some characters to the front of s.

If you have never tried to solve this problem, I suggest that you solve it, and it will help you improve your problem solving skill.

After solving it, I kept looking for better solutions. I stumbled upon another programmer's solution. It is in python, and really neat. It is really interesting, but later I found out it was wrong.
class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0 and A[index]!=A[i]):
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        print cont[-1]
        return s[cont[-1]:][::-1]+s

If you know python, please take some time to digest the Solution. By 2015-06-05, this solution is still accepted by leetcode. (Updated: LeetCode now added test cases to check this issue)

I myself looked at the Solution and saw it's interesting idea. At first, the algorithm concatenates the string and its reversed version. Then the following steps are similar to the steps for building KMP-table (or failure function) using in KMP algorithm. Why does this procedure work?

If you know KMP text searching algorithm, you will know its "lookup table" and steps to build it. Right now, I just show one important use of the table: it can show you the longest prefix of a string s that is also suffix of s (but not s itself). For example, "abcdabc" has the longest prefix which is also a suffix: "abc" (not "abcdabc" since this is the entire string!!!). To make it fun, we call this prefix is "happy substring" of s. So the happy substring of "aaaaaaaaaa" (10 a's ) is "aaaaaaaaa" (9 a's).

Now we go back and see how finding happy sub string of s can help solve the shortest palindrome problem.

Suppose that q is the shortest string added to the front of s to make the string qs is a palindrome. We can see that obviously length(q) < length(s) since ss is also a palindrome. Since qs is a palindrome, qs must end with q, or s = p+q where p is a sub string of s. Easily we see that p is also a palindrome. Therefore, in order to have shortest qs, q needs to be shortest. In turn, p is the longest palindromic sub string of s.

We call s' and q' are the reversed strings of s and q respectively. We see that s = pq, s' = q'p since p is a palindrome. So ss' = pqq'p . Now we need to find the longest p. Eureka! This also means that p is a happy sub string of the string ss'. That's how the above algorithm works!!!

However, after some thought, the above algorithm has some loophole. p is not a happy sub string of ss'! In fact, p is the longest prefix that is also a suffix of ss', but the prefix and suffix must not overlap each other. So let's make it more fun, we call "extremely happy sub string" of a string s is the longest sub string of s that is a prefix and also a suffix and this prefix and suffix must not overlap. On the other word, the "extremely happy sub string" of s must have length less than or equal half length of s. 

So it turns out the "happy sub string" of ss' is not always "extremely happy sub string" of ss'. We can easily construct an example: s = "aabba". ss'="aabbaabbaa". The happy sub string of "aabbaabbaa" is "aabbaa", while the extremely happy sub string of "aabbaabbaa" is "aa". Bang!

Hence, the correct solution should be as following, based on the observation that length(p) <= length(ss')/2.

class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0):
                if(A[index]==A[i]):
                    if index < len(s):
                        break
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        print cont[-1]
        return s[cont[-1]:][::-1]+s

Hooray!
As you can see, algorithms are interesting! And we programmers are responsible for making correct solutions carefully studying the problems. The only way for us is to keep learning, "Train dragons the hard way"!