14.1 Longest Palindromic Substring

14.1.1 Problem Metadata

14.1.2 Description

Return the longest palindromic substring contained in s.

14.1.3 Examples

Input: "babad"
Output: "bab"   // "aba" also valid

Input: "cbbd"
Output: "bb"

14.1.4 Constraints

  • 1 <= s.length <= 1000
  • s consists of digits and Englc-lish letters

14.1.5 Solution - DP via Reversed String

14.1.5.1 Walkthrough

Compute the longest common substring between s and its reverse. Matches correspond to palindromic substrings only when their indices line up (i.e., the substring reads the same forward and backward). Track the candidate with the greatest length that satisfies the index alignment rule.

14.1.5.2 Analysis

  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)

14.1.5.3 Implementation Steps

  1. Let rev = reverse(s); create dp[n][n].
  2. For each pair (i, j) update dp[i][j] similar to LCS-substring.
  3. When dp[i][j] > currentMax, ensure the substring indices align (n - 1 - j + dp[i][j] - 1 == i).
  4. Update best boundaries accordingly.

14.1.5.4 Code - Java

public String longestPalindrome(String s) {
    int n = s.length();
    String rev = new StringBuilder(s).reverse().toString();
    int[][] dp = new int[n][n];
    int maxLen = 0;
    int end = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s.charAt(i) == rev.charAt(j)) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                int beforeRev = n - 1 - j;
                if (dp[i][j] > maxLen && beforeRev + dp[i][j] - 1 == i) {
                    maxLen = dp[i][j];
                    end = i;
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }

    return s.substring(end - maxLen + 1, end + 1);
}