class Solution {
    int maxLen = 0; //儲存最長迴文子字串的長度
    int lo = 0; //儲存最長迴文子字串的起始索引
    public String longestPalindrome(String s) {
        char[] input = s.toCharArray();
        if(s.length() < 2) {
            return s;
        }
        
        for(int i = 0; i<input.length; i++) {
            expandPalindrome(input, i, i);
            expandPalindrome(input, i, i+1);
        }
        return s.substring(lo, lo+maxLen);
    }
    
    public void expandPalindrome(char[] s, int j, int k) {
        while(j >= 0 && k < s.length && s[j] == s[k]) {
            j--;
            k++;
        }
        if(maxLen < k - j - 1) { //迴文子字串的長度是 k - j - 1
            maxLen = k - j - 1;
            lo = j+1;
        }
    }
}