Longest Palindromic Substring – DP Solution and Java/C++ Implementations

Before diving into technical content, the author recounts a recent experience where a job candidate was subjected to an unusually detailed background check, noting that such checks are becoming common and sometimes involve colleagues providing favorable remarks.

The main focus then shifts to LeetCode problem 5, "Longest Palindromic Substring". The problem asks for the longest substring of a given string s that reads the same forward and backward.

Example 1: Input s = "babad" → Output "bab" (or "aba" as an alternative). Example 2: Input s = "cbbd" → Output "bb" .

Constraints: 1 <= s.length <= 1000 and s consists only of digits and English letters.

Problem analysis : A brute‑force approach enumerates all substrings and checks each for palindrome property, but this has high time complexity. A more efficient method is the center‑expansion technique, which can be further optimized using Manacher's algorithm. The article chooses to illustrate a dynamic‑programming (DP) solution.

DP definition: dp[left][right] is true if the substring s[left..right] is a palindrome. The recurrence is:

dp[left][right] = (s[left] == s[right]) && dp[left+1][right-1];

Base cases:

If left == right , the substring is a single character and thus a palindrome.

If right - left <= 2 , substrings like "aa" or "aba" are palindromes.

When filling the DP table, one must ensure that dp[left+1][right-1] is computed before dp[left][right] . Traversal can be done column‑by‑column, row‑by‑row, or diagonal‑wise, as long as the dependency order is respected.

After populating the DP matrix, the longest palindrome is tracked by maintaining the start index and maximum length.

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
> dp(length, vector
(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);
}

The article concludes with visual diagrams (omitted here) illustrating the DP table layout and traversal order.