JAVA O(n) solution


  • 0

    Manacher's Algorithm
    '''
    public class Solution {
    public String longestPalindrome(String s) {

       		char[] c=new char[s.length()*2+3];
           
           int len=c.length;
           c[0]='$';
           c[len-1]='@';
           int j=0;
           for(int i=1;i<len-1;i++)
           {
               if(i%2 == 1)
               {
                   c[i]='#';
               }
               else
               {
                   c[i]=s.charAt(j);
                   j++;
               }
           }
           j=0;
           
           int arr[]=new int[c.length];
           
           int center=0,mirr=0;
           int R=0;
           
           for(int i=1;i<c.length-1;i++)
           {
               mirr=2* center -i;
               
               if(i<R)
               {
                   arr[i]=Math.min(R-i,arr[mirr]);
               }
               
               while(c[i+(1+arr[i])] == c[i-(1+arr[i])])
               {
                   arr[i]++;
               }
               
               if(i+arr[i]>R)
               {
                   center=i;
                   R=i+arr[i];
               }
           }
           
           int max=0,index=-10;
           
           for(int i=0;i<arr.length;i++)
           {
               if(max<arr[i])
               {
                   max=arr[i];
                   index=i;
               }
           }
           
           char[] result=new char[max];
           j=0;
           for(int i=index-(max-1);i<=index+(max-1);i=i+2)
           {
               result[j]=c[i];
               j++;
           }
           String re=new String(result);
           return re;
            
            
            
        }
    

    }
    '''

    '''


Log in to reply
 

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