Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"

class Solution {
    public String longestPalindrome(String s) {
        int max = 0;
        String res = "";
        for(int i = 0; i < s.length(); i++) {
            String s1 = getLongest(s, i, i);
            String s2 = getLongest(s, i, i+1);

            if(s1.length() > max) {
                max = s1.length();
                res = s1;
            }
            if(s2.length() > max) {
                max = s2.length();
                res = s2;
            }
        }
        return res;
    }

    public String getLongest(String s, int left, int right) {
        String res = "";
        while(left >= 0 && right < s.length()) {
            if(s.charAt(left) != s.charAt(right)) break;
            left--;
            right++;
        }
        return s.substring(left+1, right);
    }
}