public String longestPalindromeDP(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int maxLen = 1;
        int index = 0;

        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        index = i;
                    }
                }
            }
        }

        return s.substring(index, index + maxLen);
    }