5. Longest Palindromic Substring

Brutal Force: O(n^2)

public class Solution {
    public String longestPalindrome(String s) {
        String maxPal="";
        for(int i=0;i<s.length();i++)
        {
            String str1=lenofPal(i, i, s);
            if(str1.length()>maxPal.length())
                maxPal=str1;
            String str2=lenofPal(i, i+1, s);
            if(str2.length()>maxPal.length())
                maxPal=str2;
        }
        return maxPal;
    }
    private String lenofPal(int l, int r, String s)
    {
        while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r))
        {
            l--;
            r++;
        }
        return s.substring(l+1,r);
    }
}

 

Manacher: O(n)

public class Solution {
    public String longestPalindrome(String s) {
        char[] arr=new char[s.length()*2+1];
        for(int i=0;i<arr.length;i++)
        {
            if(i%2==0)
                arr[i]='#';
            else
                arr[i]=s.charAt(i/2);
        }
        
        int[] len=new int[arr.length];
        int po=0;
        int mx=0;
        String ret="";
        for(int i=0;i<arr.length;i++)
        {
            if(mx>i)
                len[i]=Math.min(mx-i, len[2*po-i]);
            else
                len[i]=1;
            while(i-len[i]>=0&&i+len[i]<arr.length&&arr[i-len[i]]==arr[i+len[i]])
                len[i]++;
            if(i+len[i]>mx)
            {
                mx=i+len[i];
                po=i;
            }
            if(len[i]-1>ret.length())
                ret=s.substring((i-len[i]+1)/2,(i+len[i]-1)/2);
        }
        return ret;
    }
}