class Solution {
    //最长回文子串，动态规划，
    //dp[i][j]代表从i到j的最长回文子串的长度
    //初始化的dp[i][i] = 1
    //遍历顺序：按长度遍历，再从左到右按索引遍历
    public String longestPalindrome(String s) {
        // char[] arr = s.toCharArray();
        // 反序与原始字符串相同，动态规划
        // 如果s.substring(i,j)是回文子串，则s.substring(i+1,j-1)一定也是回文子串
        // 每一个字符一定是回文子串，判断2个长度的字符串是不是回文子串只需要判断两个字符是否相等
        // 用二维哈希表来表示所有子串是不是回文子串，行下标与列下标的最大差值代表长度
    //    int len = arr.length;
    //    if(len < 2){     //长度小于2说明是动态数组
    //        return s;
    //    }
    //    boolean[][] hash = new boolean[len][len];
    //    int maxLen = 1;
    //    int begin = 0;
    //     for(int i = 0 ; i < len; i++){
    //         hash[i][i] = true;  // 单个字符一定是回文串
    //     }
    //     for(int L = 2; L <= len; L++){  //L代表的长度
    //         for(int i = 0 ; i < len; i++){   //左边界，字符串的起始下标
    //             int j = L + i - 1; //子字符串的长度为L, j - i + 1 = L;
    //             if( j >= len){
    //                 break;
    //             }
    //             if(arr[i] != arr[j]){ // 子字符串长度小于等于3的时候，只需要看左右边界
    //                 hash[i][j] = false; // 子字符串长度>3的时候，hash[i][j] = hash[i+1][j-1];
    //             }else {
    //                 if(L <= 3){
    //                     hash[i][j] = true;
    //                 }else{
    //                     hash[i][j] = hash[i+1][j-1];
    //                 }
    //             }
    //             if(hash[i][j]&& L > maxLen){
    //                 maxLen = L;
    //                 begin = i;
    //             }
    //         } 
    //     }
    //     return s.substring(begin,begin+maxLen); // 不包括begin+maxLen
        int n = s.length();
        if (n == 1) {
            return s;
        }
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        int maxLen = 1;
        int begin = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < n;j++) {
                int k = j + i - 1;
                if(k >= n) {
                    break;
                }
                if (i <= 3) {
                    if (s.charAt(j) == s.charAt(k)) {
                        dp[j][k] = true;
                    }else {
                        dp[j][k] = false;
                    }
                } else {
                     if (s.charAt(j) == s.charAt(k)) {
                        dp[j][k] = dp[j +1][k - 1] ;
                    }else {
                        dp[j][k] = false;
                    }
                }
                if (dp[j][k] && i > maxLen ) {
                    maxLen = i;
                    begin = j;
                }
            }
        }
        return s.substring(begin,begin+maxLen);

    }
}