5. Longest Palindromic Substring

** O(n^2)
class Solution {
    public String longestPalindrome(String s) {
        int start = 0;
        int end = 0;
        for(int i = 0;i <s.length(); i++)
        {
            int len1 = expandMiddle(s, i, i);
            int len2 = expandMiddle(s, i, i+1);
            int len = Math.max(len1, len2);
            if(len>end-start)
            {
                start = i-((len-1)/2);
                end = i+(len/2);
            }
        }
        return s.substring(start, end+1);
    }
    
    public int expandMiddle(String s, int left, int right)
    {
        while( left >= 0 && right <s.length() && s.charAt(left) == s.charAt(right))
        {
            left--;
            right++;
        }
        
        return right-left-1;
    }
}

** Brute force O(n^3)
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        String res = "";
        for(int i = 0;i <len; i++)
        {
            for(int j=i+1; j<=len; j++)
            {
                String str = s.substring(i,j);
                String str1 = "";
                int k = str.length()-1;
                while(k>=0)
                {
                    str1 = str1 + str.charAt(k);
                    k--;
                }
                if(str.equals(str1) && str.length() > res.length()) res = str;
            }
        }
        return res;
    }
}