// @Title: 最长回文子串 (Longest Palindromic Substring)
// @Author: qisiii
// @Date: 2024-04-11 00:12:53
// @Runtime: 102 ms
// @Memory: 46.1 MB
// @comment: 动态规划，B[i][j]=B[i+1][j-1]&str[i]==str[j]
// @flag: ORANGE
class Solution {
    public String longestPalindrome(String s) {
        char[] chars=s.toCharArray();
        boolean[][] B=new boolean[chars.length][chars.length];
        int max=0;String result="";
        for(int j=0;j<chars.length;j++){
            for(int i=0;i<j+1;i++){
                boolean isB=false;
                if(i==j){
                    isB=true;
                }else{
                    if(chars[i]==chars[j]){
                        if(j-i<3){
                            isB=true;
                        }else{
                            isB=B[i+1][j-1];
                        }
                        
                    }
                }
                B[i][j]=isB;
                if(isB&&max<j-i+1){
                    max=j-i+1;
                    result=s.substring(i,j+1);
                }
            }
        }
        return result;
    }
}

// @Title: 最长回文子串 (Longest Palindromic Substring)
// @Author: qisiii
// @Date: 2021-12-21 13:21:06
// @Runtime: 172 ms
// @Memory: 43.4 MB
// @comment: 
// @flag: 
class Solution {
    public static String longestPalindrome(String s) {
        if (s.length()<=0){
            return "";
        }
        boolean[][] value=new boolean[s.length()][s.length()];
        char[] chars = s.toCharArray();
        int max=1;
        String result=String.valueOf(chars[0]);
        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <=j; i++) {
                boolean isPalindrome=false;
                if (i==j){
                    isPalindrome=true;
                }else if(i+1>j-1&&chars[i]==chars[j]){
                    isPalindrome=true;
                }else if(i+1<s.length()&&j-1>=0){
                    isPalindrome=value[i+1][j-1]&&chars[i]==chars[j];
                }
                value[i][j]=isPalindrome;
                if (isPalindrome&&j-i+1>max){
                    max=j-i+1;
                    result=s.substring(i,j+1);
                }
            }
        }
        return result;
    }
}