Longest Palindromic Subsequence — Solution

Problem

Given a string, find the length of the longest subsequence that reads the same forwards and backwards. A subsequence keeps characters in their original order but can skip any number of characters. For "bbbab", the subsequence "bbbb" is a palindrome of length 4 — the longest possible.

• Input: s = "bbbab"
• Output: 4
• Explanation: Skipping the 'a' leaves "bbbb", which is a 4-character palindrome.

Counter-example: "cbbd" has LPS of length 2 ("bb") — you can't do better because 'c' and 'd' differ and 'c' and 'b' differ, so no 3-character palindromic subsequence exists.

Intuition

When you look at the two ends of a substring, you have a binary choice: if they match, they can both anchor the palindrome and the problem shrinks to the middle; if they don't match, one end must be excluded, so you try both exclusions and take the better result. This optimal substructure — where the answer for s[i..j] depends only on answers for smaller subranges — is the signature of interval DP.

Solution — 2D Bottom-Up DP

Define dp[i][j] as the length of the longest palindromic subsequence in s[i..j]. Fill by increasing substring length so that shorter subproblems are always solved before the longer ones that depend on them.

1. Initialize dp[i][i] = 1 — every single character is a palindrome of length 1.
2. Iterate over substring lengths from 2 up to n.
3. For each length, slide a window [start, end] across the string.
4. If s[start] == s[end], both characters join the palindrome: add 2 to the inner answer dp[start+1][end-1] (0 if the window is exactly 2 characters wide).
5. Otherwise, the ends don't match: take max(dp[start+1][end], dp[start][end-1]) to exclude whichever end hurts less.
6. Return dp[0][n-1].

1def longestPalindromeSubseq(self, s: str) -> int:
2    n = len(s)
3    dp = [[0] * n for _ in range(n)]
4
5    for i in range(n):
6        dp[i][i] = 1  # every single character is its own palindrome
7
8    for length in range(2, n + 1):
9        for start in range(n - length + 1):
10            end = start + length - 1
11            if s[start] == s[end]:
12                # matching ends extend the inner palindrome by 2
13                inner = dp[start + 1][end - 1] if length > 2 else 0
14                dp[start][end] = inner + 2
15            else:
16                # drop whichever end gives the longer subsequence
17                dp[start][end] = max(dp[start + 1][end], dp[start][end - 1])
18
19    return dp[0][n - 1]

Time: O(n²) — each of the n² cells is filled in constant work.

Space: O(n²) — the full DP table; reducible to O(n) by keeping only two rows, but rarely needed in interviews.

Complexity Summary

Common Mistakes

• Accessing dp[start+1][end-1] when the window is only 2 characters wide — when start+1 > end-1, that cell represents an empty substring and should be treated as 0, not read from the table (the length > 2 guard handles this).
• Filling the table row-by-row instead of by increasing substring length — dp[i][j] depends on dp[i+1][j-1], which sits one row below and one column to the left; filling row-by-row reads that cell before it is computed.
• Confusing LPS (subsequence) with LPS (substring) — the longest palindromic substring is a completely different problem requiring expand-around-center or Manacher's algorithm; the subsequence version allows skips.
• Returning dp[n-1][0] instead of dp[0][n-1] — the answer for the full string lives at dp[0][n-1]; the lower-left triangle of the table is never filled and stays 0.
• Thinking LPS equals n minus edit distance to the reverse — while mathematically equivalent (LPS = LCS(s, reversed s)), computing it via LCS adds complexity and is harder to explain under pressure.

Related Problems

• longest-common-subsequence — LPS can be derived as LCS(s, reverse(s)); same 2D table-filling pattern
• palindromic-substrings — counts palindromic substrings using the same interval expansion idea
• longest-palindromic-substring — contiguous variant; solved by expand-around-center rather than DP, which clarifies why subsequence and substring differ
• edit-distance — same 2D DP structure where each cell depends on three adjacent cells
• word-break — 1D DP with a similar "try all split points" recurrence, good warmup before 2D interval DP