Longest Palindromic Substring.

Problem. Given a string, return its longest contiguous substring that is a palindrome. "babad" → "bab" (or "aba").

Brute force — O(n³)

Check all O(n²) substrings, each palindrome-test O(n). Too slow, but it frames the two better approaches.

Interval DP — O(n²) time and space

State dp[i][j] = is s[i..j] a palindrome? A range is a palindrome when its ends match and the interior is a palindrome:

dp[i][j] = (s[i] == s[j]) && (j - i < 3 || dp[i+1][j-1])

j - i < 3 covers length-1 and length-2 base cases. Fill by increasing length so the inner range is already computed:

String longestPalindrome(String s) {
    int n = s.length(), start = 0, maxLen = 1;
    boolean[][] dp = new boolean[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = true;        // length 1
    for (int len = 2; len <= n; len++)                  // fill by length
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (len > maxLen) { start = i; maxLen = len; }
            }
        }
    return s.substring(start, start + maxLen);
}

Optimal in practice — expand around center, O(n²) time, O(1) space

Every palindrome has a center: one of n characters (odd length) or one of n-1 gaps (even length). Expand outward from each of the 2n-1 centers while characters match:

String longestPalindrome(String s) {
    if (s.isEmpty()) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int odd = expand(s, i, i);          // center on a char
        int even = expand(s, i, i + 1);     // center between chars
        int len = Math.max(odd, even);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}
private int expand(String s, int lo, int hi) {
    while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
        lo--; hi++;
    }
    return hi - lo - 1;                      // length of the matched palindrome
}

Same O(n²) time but only O(1) space, and faster constants since it short-circuits on mismatch.