Longest Palindromic Subsequence

LPS asks: what is the longest subsequence of a string that reads the same forward and backward, and it works by shrinking the string from both ends — if the outer characters match, they can anchor a palindrome around whatever palindrome exists inside; if they don't match, the best palindrome must sacrifice one end or the other, so you take the better of the two smaller subproblems.

Recognize the pattern

• Problem talks about a subsequence (not substring) that must be a palindrome.
• Answer only needs a length/count, or the palindrome itself, over one string.
• Naturally described by two shrinking pointers i (left) and j (right) over a range.
• It is the twin of Longest Common Subsequence: LPS(s) = LCS(s, reverse(s)).

Brute force → optimal

Brute force: generate all 2^n subsequences, check each for being a palindrome, keep the longest. Cost: O(2^n · n) time, O(n) space (recursion) — infeasible past n≈20.

Optimal (interval DP): define dp[i][j] = length of the LPS within s[i..j] (inclusive). For every substring range, decide based on whether the two boundary characters match:

dp[i][j] =
  1                                  if i == j
  2 + dp[i+1][j-1]                   if i < j and s[i] == s[j]
  max(dp[i+1][j], dp[i][j-1])        if i < j and s[i] != s[j]

Base case: single character is a palindrome of length 1; empty range (i>j) has length 0.

Complexity, derived

The state space is every pair (i, j) with 0 ≤ i ≤ j < n, roughly n²/2 distinct subproblems. Each state does O(1) work (a comparison plus one or two array lookups), so total time is O(n²). Because dp[i][j] only depends on smaller ranges (i+1,j-1, i+1,j, i,j-1), filling the table by increasing range length len = j-i guarantees dependencies are already computed. Space for the full table is O(n²); it can be compressed to O(n) with two rolling rows if only the length (not the palindrome text) is needed, since each row only reads the row below it plus one earlier cell in the same row.

Worked example: s = "cddpd" (n=5)

Indices: c(0) d(1) d(2) p(3) d(4). Fill by increasing length.

Answer: dp[0][4] = 3, matching "ddd".

Java implementation

class Solution {
    public int longestPalinSubseq(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = 2 + (len == 2 ? 0 : dp[i + 1][j - 1]);
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

Pitfalls

• Confusing subsequence with substring — LPS allows deleting characters; Longest Palindromic Substring requires contiguity and is a different problem with different DP (expand-around-center or Manacher's).
• Not guarding the empty string: for n == 0 the table is 0×0 and no loop ever runs, so dp[0][n-1] becomes dp[0][-1] and throws ArrayIndexOutOfBoundsException. Return 0 immediately when n == 0.
• Forgetting the guard for len == 2: when len == 2, i+1 > j-1, so the inner range (i+1, j-1) is empty and does not correspond to a valid table cell. Treat it as 0 directly (as the code above does) instead of reading dp[i+1][j-1], which for len == 2 would index outside the intended range and return a stale or wrong value.
• Filling by row/column index instead of by increasing length breaks the dependency order and reads uninitialized cells.
• Using O(n²) space for n up to 1000 is 1M ints — fine, but for larger n switch to the O(n) rolling-array version if only the length is needed.

When to use / when not — trade-offs

Use interval DP when the answer decomposes by shrinking both ends of a range and the match/mismatch of the endpoints determines the recurrence (also used in palindrome partitioning, burst balloons, matrix chain multiplication). Space is O(n²), which is expensive for very large n (say n > 10⁴, giving 10⁸ cells) — if only the count and not the reconstructed string is needed, use the O(n) rolling-row optimization. As an alternative, LPS(s) = LCS(s, reverse(s)) reduces it to the more general Longest Common Subsequence algorithm — same O(n²) time/space, useful if you already have an LCS routine, but it costs roughly 2x the memory/compute of the direct interval DP if you only need this one problem solved.

Takeaways

• LPS is interval DP: state = a range [i,j], transition shrinks from both ends based on endpoint match.
• Fill order must go by increasing range length, not row-major order.
• O(n²) time and space are both derived directly from the number of (i,j) pairs and O(1) work per pair; compressible to O(n) space if reconstruction isn't needed.
• Edge sanity checks: empty → 0; single char → 1; "bb" → 2; "agbdba" → 5 (keeping the palindrome a·b·d·b·a).

Recall: Why must the DP table for LPS be filled in order of increasing substring length rather than by row index?

Adapted and expanded from the interview-prep source problem "Longest Palindromic Subsequence" with derivation, worked trace, complexity analysis, and trade-off discussion added by the study guide.