Longest Palindromic Subsequence — Interval DP Done Right

Problem Statement#

Given a string s, return the length of the longest palindromic subsequence in it. A subsequence is formed by deleting zero or more characters without changing the order of the remaining ones; it does not have to be contiguous.

Example: s = "bbbab" returns 4. The longest palindromic subsequence is "bbbb", obtained by deleting the a.

Example: s = "cbbd" returns 2. The longest palindromic subsequence is "bb".

Constraints: 1 is less than or equal to s.length is less than or equal to 1000. The bound rules out 2^n brute force and demands a polynomial DP.

Why This Problem Matters#

Longest Palindromic Subsequence (LPS) is the gateway problem to interval DP. Amazon, Google, Microsoft, and Adobe ask it because it cleanly tests four skills: defining a 2D DP state on a substring interval, ordering the table fill so that dependencies are resolved, recognizing the connection to Longest Common Subsequence, and applying space optimization on a 2D table.

If you understand LPS deeply, you basically understand Strange Printer, Burst Balloons, Matrix Chain Multiplication, and Palindrome Partitioning II — they all share the same "fill by interval length" pattern.

The Core Insight (Recurrence)#

Define dp[i][j] as the length of the longest palindromic subsequence in the substring s[i..j] (both indices inclusive). The recurrence has two cases:

• If s[i] == s[j]: the two ends can both belong to the palindrome. dp[i][j] = dp[i+1][j-1] + 2.
• Otherwise we drop one side: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

Base cases: dp[i][i] = 1 (single character) and dp[i][i-1] = 0 (empty interval, important when i and j are adjacent and equal characters reduce to it).

The key dependency: dp[i][j] needs values with strictly smaller j - i, so we must iterate by increasing interval length, not by index. That ordering is what makes interval DP feel different from typical row-major tabulation.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down recursion solve(i, j) mirrors the recurrence directly. Memoizing on (i, j) gives O(n^2) states each computed in O(1), so O(n^2) time and O(n^2) memory plus recursion stack.

Tabulation: allocate dp[n][n], set diagonal to 1, then loop length = 2 to n and inner index i = 0 to n - length. Compute j = i + length - 1. The table fills along anti-diagonals.

Space optimization: each dp[i][j] only reads dp[i+1][j-1], dp[i+1][j], and dp[i][j-1]. Storing two rows (current and previous in interval-length order) reduces memory to O(n). For interview demos the full 2D table is clearer, but the O(n) variant is a real win on memory-constrained systems.

There is also a slick reduction: LPS of s equals Longest Common Subsequence of s and reverse(s). That uses the standard LCS DP and gives an O(n^2) solution with the same complexity — useful if the interviewer just asked you LCS.

Visual Dry Run (DP Table Trace)#

Trace s = "bbbab" (length 5).

Initialize the diagonal: dp[i][i] = 1 for all i.

Length 2 — pairs (0,1), (1,2), (2,3), (3,4):

• s[0]=b, s[1]=b -> dp[0][1] = 0 + 2 = 2.
• s[1]=b, s[2]=b -> dp[1][2] = 2.
• s[2]=b, s[3]=a -> dp[2][3] = max(1,1) = 1.
• s[3]=a, s[4]=b -> dp[3][4] = max(1,1) = 1.

Length 3:

• s[0]=b, s[2]=b -> dp[0][2] = dp[1][1] + 2 = 3.
• s[1]=b, s[3]=a -> dp[1][3] = max(dp[2][3], dp[1][2]) = 2.
• s[2]=b, s[4]=b -> dp[2][4] = dp[3][3] + 2 = 3.

Length 4:

• s[0]=b, s[3]=a -> dp[0][3] = max(dp[1][3], dp[0][2]) = 3.
• s[1]=b, s[4]=b -> dp[1][4] = dp[2][3] + 2 = 3.

Length 5:

• s[0]=b, s[4]=b -> dp[0][4] = dp[1][3] + 2 = 4.

Answer: dp[0][4] = 4, matching the expected "bbbb".

Optimized Solution — Space-Optimized Python and JavaScript#

Python#

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        # dp[j] stores the LPS for the current "i" row.
        dp = [0] * n
        for i in range(n - 1, -1, -1):
            new_dp = [0] * n
            new_dp[i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    new_dp[j] = dp[j - 1] + 2
                else:
                    new_dp[j] = max(dp[j], new_dp[j - 1])
            dp = new_dp
        return dp[n - 1]

JavaScript#

var longestPalindromeSubseq = function (s) {
  const n = s.length;
  let dp = new Array(n).fill(0);
  for (let i = n - 1; i >= 0; i -= 1) {
    const next = new Array(n).fill(0);
    next[i] = 1;
    for (let j = i + 1; j < n; j += 1) {
      if (s[i] === s[j]) {
        next[j] = dp[j - 1] + 2;
      } else {
        next[j] = Math.max(dp[j], next[j - 1]);
      }
    }
    dp = next;
  }
  return dp[n - 1];
};

Complexity Analysis#

• Time: O(n^2). Each cell computes in O(1) and there are O(n^2) cells.
• Space: O(n^2) for the textbook tabulation, O(n) for the rolling-row optimization, O(n) plus stack for memoization.
• The LCS reduction also runs in O(n^2) time and space — useful if you have already solved LCS in the same interview.

Common Mistakes#

• Filling the table row by row. That breaks dependencies because dp[i][j] needs dp[i+1][j-1]. Always iterate by interval length.
• Forgetting dp[i][i] = 1. A single character is a palindrome of length 1; missing it gives off-by-ones throughout.
• Confusing subsequence with substring. Substring needs contiguity; the recurrence and answer differ. LeetCode 5 asks substring, LeetCode 516 asks subsequence.
• Returning the subsequence string by mistake. The problem asks for length only. If asked for the actual subsequence, parent-pointer reconstruction is a follow-up.
• Using only the LCS reduction without explanation. It works but interviewers reward direct interval DP reasoning.

Interview Tips#

• State the recurrence and base case before writing code. The cleanest sentence: "If both ends match, take them both and recurse inward; otherwise drop one end."
• Demonstrate the diagonal fill order with a small example on the whiteboard. Many candidates lose points by writing a row-major loop and silently producing wrong answers.
• Mention space optimization as a bonus — it shows production thinking. The O(n) version uses two rolling rows.
• Connect to LCS by noting LPS(s) == LCS(s, reverse(s)). That insight wins senior-level brownie points.

Follow-up Questions#

• Reconstruct the actual longest palindromic subsequence string. Hint: track the recurrence choice in a parallel table.
• Count the number of distinct longest palindromic subsequences (LeetCode 730). Same shape, different transition.
• Find the minimum number of insertions to make s a palindrome (LeetCode 1312). Answer: n - LPS(s).
• Solve LPS for very large n (think 10^5). The DP is too heavy; the problem becomes intractable in general.

Key Takeaways#

• Longest Palindromic Subsequence is the canonical interval DP problem with a two-line recurrence and a strict diagonal fill order.
• The state dp[i][j] represents the answer on the substring s[i..j] and depends only on neighbors with strictly smaller intervals.
• Optimal substructure plus overlapping subproblems make it a textbook memoization or tabulation candidate; both run in O(n^2) time.
• Space optimization with rolling rows brings memory to O(n) — interviewers love seeing it.
• The LCS-of-s-and-reverse(s) reduction is a beautiful equivalence but should supplement, not replace, the direct DP narrative.
• Mastering this recurrence unlocks Strange Printer, Burst Balloons, and Matrix Chain Multiplication, which all use the same length-first traversal pattern.