给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 1 || s.length() == 0) return s;

        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int beginIndex = 0;
        int maxLen = 1;

        for (int j = 0; j < len ; j++) {

            for (int i = 0 ; i <= j ; i++){
                if (s.charAt(i) == s.charAt(j)){
                    if (j - i < 2){
                        dp[i][j] = true;
                    }
                    else dp[i][j] = dp[i+1][j-1];
                }
                else dp[i][j] = false;

                if (dp[i][j] && j-i+1 > maxLen){
                    beginIndex = i;
                    maxLen = j - i + 1;
                }
            }
        }

        return s.substring(beginIndex,beginIndex+maxLen);    
    }
}