Longest Palindromic Substring

A palindrome is symmetric around a center, so instead of checking all O(n²) substrings from scratch, you can grow outward from each possible center (there are 2n-1 of them, counting between-character centers for even-length palindromes) and stop the moment the two ends stop matching — the DP variant instead builds up the answer for longer substrings from the verified answers for shorter ones, since a substring s[i..j] is a palindrome iff s[i]==s[j] AND s[i+1..j-1] is a palindrome (or has length ≤ 1).

Recognize the pattern

• Problem talks about a contiguous substring (not subsequence) that reads the same forwards and backwards.
• Asked for the longest / count of palindromic substrings, not just "is this string a palindrome".
• Constraints are small-ish (n ≤ 1000–5000) — a hint that O(n²) is the intended ceiling, not O(n).
• Recurrence naturally shrinks the problem from the outside in: strip the two ends, recurse on the middle.

Brute force → optimal

Brute force wastes work: checking s[i..j] takes O(j-i) time on its own, and there are O(n²) pairs (i,j), giving O(n³). The DP/expand-around-center approaches cut the per-substring check to O(1) by reusing previously computed results, dropping to O(n²).

Complexity, derived

DP table version: dp[i][j] = true iff s[i]==s[j] and (j-i<2 or dp[i+1][j-1]). We fill the table by increasing substring length L = 1..n. For each L there are (n-L+1) starting positions i, and each cell costs O(1) to compute from an already-filled cell. Total work = Σ_{L=1}^{n} (n-L+1) · O(1) = O(n²) operations. Space is the full n×n boolean table = O(n²).

Expand-around-center version: there are exactly 2n-1 centers (n single-character centers + n-1 between-character centers for even-length palindromes). Expanding from one center costs O(k) where k is the palindrome's half-length, and in the worst case (all same character, e.g. "aaaa") a center can expand O(n) steps. Summed over all centers, worst case is O(n) centers × O(n) expansion = O(n²) time, O(1) extra space since no table is stored.

Worked example: s = "cddpd"

Indices: s[0]='c', s[1]='d', s[2]='d', s[3]='p', s[4]='d'. Using expand-around-center, try each odd center (i) and each even center (between i,i+1):

Best found: "dpd", length 3 — the even-center match at (1,2) produces "dd" (length 2), which is a real intermediate result but is beaten by the odd-center-3 result, matching the expected output.

Reference implementation (expand around center)

public class LongestPalindromicSubstring {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, maxLen = 1;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i);       // odd length, center at i
            int len2 = expand(s, i, i + 1);   // even length, center between i,i+1
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        return s.substring(start, start + maxLen);
    }

    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1; // length of palindrome found
    }
}

Pitfalls

• Forgetting the even-length centers (between characters) — misses palindromes like "abba".
• Off-by-one when converting expansion bounds back to substring indices (start = i - (len-1)/2 must account for both parities).
• Using recursion for the DP without memoization — recomputes dp[i+1][j-1] exponentially many times.
• Confusing substring (contiguous) with subsequence (can skip characters) — Longest Palindromic Subsequence is a different problem solved with a different (LCS-based) DP.

When to use / when not

Use expand-around-center when you just need the longest palindromic substring and want O(n²) time with O(1) extra space — simplest to code correctly under interview pressure. Use the DP table when you also need to answer "is s[i..j] a palindrome?" for arbitrary ranges afterward (e.g. counting all palindromic substrings), since the table gives O(1) lookups post-construction at the cost of O(n²) space. Reach for Manacher's algorithm only when n is large (10⁴–10⁶) and true O(n) is required — it's correct but fiddly to implement from memory, so it's a poor default choice unless the constraints demand it.

Takeaways

• Palindromes are symmetric, so build outward from centers or inward from a verified inner interval — never re-check from scratch.
• There are 2n-1 centers (n odd, n-1 even) — always handle both parities, and note that a smaller intermediate match (like "dd" at the (1,2) even center) can still lose to a longer result elsewhere.
• DP table trades O(n²) space for O(1) range-palindrome queries; expand-around-center trades that away for O(1) space.
• Classic trap input: "babad" has two valid answers, "bab" and "aba" (both length 3) — the problem accepts either, so don't assume a unique longest palindrome.

Recall: Why does expand-around-center need to try 2n-1 centers instead of just n?

Sources: CLRS-style substring DP treatment; standard expand-around-center technique as used in LeetCode 5 (Longest Palindromic Substring); Manacher's algorithm for the O(n) extension.