Master the Longest Palindromic Substring Problem with DP in Java & C++

Problem Description

Given a string s, find the longest palindromic substring. A palindrome reads the same forward and backward.

Examples

Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Input: s = "cbbd" Output: "bb"

1 ≤ s.length ≤ 1000

s consists only of digits and English letters.

Problem Analysis

The simplest solution enumerates all substrings and checks each for palindrome, which is O(n³). A better approach is center expansion, but still O(n²). The most efficient classic solution is the Manacher algorithm, but here we focus on a dynamic programming (DP) method.

Dynamic Programming Solution

Define dp[left][right] as true if the substring s[left…right] is a palindrome. The recurrence is:

dp[left][right] = (s[left] == s[right]) && (right - left <= 2 || dp[left+1][right-1])

When computing dp[left][right], dp[left+1][right-1] must already be known, so we iterate the table from shorter substrings to longer ones (e.g., by increasing right and decreasing left, or by diagonal order).

Java Implementation

public String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    int length = s.length();
    boolean[][] dp = new boolean[length][length];
    for (int right = 1; right < length; right++) {
        for (int left = 0; left < right; left++) {
            if (s.charAt(left) != s.charAt(right)) continue;
            if (right - left <= 2) {
                dp[left][right] = true;
            } else {
                dp[left][right] = dp[left + 1][right - 1];
            }
            if (dp[left][right] && right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
        }
    }
    return s.substring(start, start + maxLen);
}

C++ Implementation

string longestPalindrome(string s) {
    int start = 0, maxLen = 1;
    int length = s.size();
    vector<vector<int>> dp(length, vector<int>(length));
    for (int right = 1; right < length; right++) {
        for (int left = 0; left < right; left++) {
            if (s[left] != s[right]) continue;
            if (right - left <= 2) {
                dp[left][right] = true;
            } else {
                dp[left][right] = dp[left + 1][right - 1];
            }
            if (dp[left][right] && right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
        }
    }
    return s.substr(start, maxLen);
}