package LeetCode;

public class LC_5 {
    public static String longestPalindrome(String s) {
        //if (s.length() == 1) return s;
        int start = 0;
        int maxLen = 1;
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = s.length() - 1; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        if (maxLen < j - i + 1) {
                            maxLen = j - i + 1;
                            start = i;
                        }
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (maxLen < j - i + 1) {
                            maxLen = j - i + 1;
                            start = i;
                        }
                    }
                }
                System.out.println("i= " + i + " ,j= " + j + " ,start = " + start + " ,maxLen= " + maxLen);
            }
            System.out.println(dp[1][3]);
        }
        return s.substring(start, start + maxLen);
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("aaaaa"));
    }
}