1class Solution {2    public String longestPalindrome(String s) {3        int n = s.length(), start = 0, best = 0;4        boolean[][] dp = new boolean[n][n];5        for (int len = 1; len <= n; len++) {6            for (int left = 0; left + len <= n; left++) {7                int right = left + len - 1;8                dp[left][right] = s.charAt(left) == s.charAt(right)9                    && (len <= 3 || dp[left + 1][right - 1]);10                if (dp[left][right] && len > best) {11                    start = left; best = len;12                }13            }14        }15        return s.substring(start, start + best);16    }17}