Java O(N) solution based on Manacher's algorithm faster than 97.16%


  • 0

    Basically the code works as following:-

    case 1: This is a new sequence so we will have to calculate the length of palindrome sequence this happens when (i>r-1) in the below solution. we initialize the DP to be equal to 0 and then add +1 to the DP till characters at both the sides are equal.

    case 2: when the centre in consideration now is on the right of an already found palindrome substring and in the boundary of the palindrome found:

    • case 2.1: if the length of palindrome substring found on the left side of the palindrome whose right hand side is the current centre is within the boundary of the bigger palindrome then the length of palindrome on right hand side is same as denoted by centre on right hand side.
    • case 2.2 if the length of palindrome substring found on the left side of the palindrome whose right hand side is the current centre is within the boundary of the bigger palindrome then the length of palindrome on right hand side is greater than or equal to length denoted by centre on right hand side.

    Complexity consideration
    for case 1 it takes N.
    for case 2 no comparisons are required.
    for case 3. we make use of what has already ben discovered all the time.

    So summing it up the complexity is < 2N which is O(N)

    public class Solution {
        public String longestPalindrome(String s) {
            if(s==null||s.length()<=1)
                return s;
            char[] sArray= s.toCharArray();
            char[] s2Array = new char[2*sArray.length+1];
            for(int i=0;i<s2Array.length-1;i+=2){
                s2Array[i]='|';
                s2Array[i+1]=sArray[i/2];
            }
            s2Array[s2Array.length-1]='|';
            int[] dp = new int[s2Array.length];
            int c=0,r=0;
            int m=0,n=0;
            int len = 0, pos = 0;
            for(int i=1;i<s2Array.length;i++){
                if(i>r-1){
                    dp[i]=0;
                    m=i-1;
                    n=i+1;
                }else{
                    int i2=c*2-i;//c-dp[c]+r-i = c-dp[c]+dp[c]+c-i
                    if(dp[i2]+i<r){
                        dp[i]=dp[i2];
                        m=-1;
                    }else {
                        dp[i]=r-i;
                        n = r+1; 
                        m = i*2-n;
                    }
                }
                while(m>=0&&n<s2Array.length&&s2Array[m]==s2Array[n]){
                    dp[i]++;
                    m--;
                    n++;
                }
                if(r<i+dp[i]){
                    c=i;
                    r=i+dp[i];
                }
                if(len<dp[i]){
                    len=dp[i];
                    pos=i;
                }
                if(i>s2Array.length-1 && dp[i]>(s2Array.length-i)/2){
                    break;
                }
            }
            char[] resultTemp = Arrays.copyOfRange(s2Array, pos-len, pos+len+1);
            char[] result = new char[(resultTemp.length-1)/2];
            for (int i = 0; i<result.length; i++) {
                result[i] = resultTemp[i*2+1];
            }
            return String.valueOf(result);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.