//   b a b a d
// b T        F
// a   T   T
// b     T
// a       T
// d F F F F T

// Longer up and to the right
// Shorter is down and to the left
// Fill from bottom right to up?
//   c b b d
// c T
// b   T
// b     T
// d       T

//   a a a a
// a T
// a   T
// a     T T
// a       T
class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        String max = null;

        boolean[][] dp = new boolean[length][length];

        for(int i = length - 1; i>= 0; i--) {
            for(int j = i; j<length; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);

                if (dp[i][j] && (max == null || j - i + 1 > max.length())) {
                    max = s.substring(i, j + 1);
                }
            }
        }
        return max;
    }
}