version at: 2022-04-22

/**
1. 最长回文子串,每个最长回文串在它两侧加上同样的字符一定可以变成更长的回文串 -> 
    奇数子串 -> 每个点向左右扩展的最大长度
    偶数字串 -> 相邻且相等的两个点向左右扩展的最大长度
*/

class Solution {
    public String longestPalindrome(String s) {
        if (s == null) return s;

        String r =  "";
        for (int i = 0; i < s.length(); i++) {
            String s1 = getPaliStringHalfLength(s, i, i);
            if (s1.length() > r.length()) r= s1;

            String s2 = getPaliStringHalfLength(s, i, i+1);    
            if (s2.length() > r.length()) r= s2;
        }

        return r;
    }

    public String getPaliStringHalfLength(String s, int l, int r) {
        while (0 <= l && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }

        return s.substring(l+1, r);
    }
}

/*
1.如果一个字符串是回文，同时扩展左右两边后仍然相等的话会变成更长的回文
2.奇数回文按一个点扩展，偶数回文按2个相邻且相同的扩展
*/

/* 区间DP 效率较低，因为结果要再次遍历
1. 状态定义：f[i][j] 表示i~j是回文串
2. 状态计算：f[i][j] = f[i+1][j-1]
3. 边界： f[i][i] = true , f[i][i+1] = s[i] == s[i+1]
*/

class Solution {
    int start = 0 ,end = 0;

    public String longestPalindrome(String s) {

        if (s == null || s.length() == 0) return s;

        int n = s.length();
        boolean[][] f = new boolean[n+2][n+2];
        for (int i = 1 ; i <= n ; i++) {
            f[i][i] = true;
            if (i < n && s.charAt(i) == s.charAt(i-1)) f[i][i+1] = true;
        }

        for (int len = 3; len <= n; len ++ ){
            for (int i = 1; i + len -1 <= n; i++){
                int j = i + len -1;
                if (i+1 <= j-1 && s.charAt(i-1) == s.charAt(j-1) && f[i+1][j-1]) f[i][j] = true;
            }
        }

        int start = 1 ,end = 1;
        for (int i = 1; i <= n ; i ++){
            for (int j = i;  j <= n ; j++){
                if (f[i][j] && j -i > end - start){
                    end = j;
                    start = i;
                }
            }
        }
        return s.substring(start-1, end);
    }



    public String longestPalindrome2(String s) {
        if (s == null || s.length() == 0) return s;

        char[] array = s.toCharArray();
        for (int i = 0 ; i < array.length; i ++){
            findBoundPalindrome(array, i, i);
            if (i < array.length - 1 && array[i] == array[i + 1]){
                findBoundPalindrome(array, i, i+1);
            }
        }
        return String.valueOf(Arrays.copyOfRange(array, start, end+1));
    }

    public void findBoundPalindrome(char[] array, int l, int r){
        while (0 < l && r < array.length - 1 && array[l-1] == array[r + 1]){
            l--;
            r++;
        }
        if (r-l > end - start){
            end = r;
            start = l;
        }
    }

}