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();
    }
}