Longest Palindromic Subsequence
Find the longest subsequence of a string that reads the same both ways with interval DP over s[i..j]: matching ends wrap the best inside.
Problem Understanding
Longest Palindromic Subsequence: given a string s, return the length of the longest subsequence that is a palindrome. A subsequence keeps the letters' order but may skip any of them.
Examples: "bbbab" returns 4 ("bbbb"); "cbbd" returns 2 ("bb").
The Intuition: Look at the Two Ends
Take any substring s[i..j] and look only at its two end letters:
- They match: they can be the outer pair of the palindrome, wrapped around the best palindrome strictly inside.
dp[i][j] = dp[i+1][j-1] + 2. - They differ: at least one of them is not in the answer, so drop the left end or the right end and keep the better:
max(dp[i+1][j], dp[i][j-1]). - One letter is a palindrome of length 1.
Every state is an interval, so this is interval dynamic programming. The "match: diagonal + something, otherwise max of two neighbours" shape is the same as Longest Common Subsequence, and in fact the LCS of s and reverse(s) gives the same length. If the palindrome must be contiguous, it is a different problem: Longest Palindromic Substring or counting them in Palindromic Substrings.
Interactive Walkthrough
ROW i = START · COLUMN j = END
BOTTOM ROW FIRST
b
b
b
a
b
b
b
b
a
b
length
:
one
:
dp[i][j] will hold the longest palindromic subsequence of s[i..j]. Fill rows from the bottom (i = 4) up
Next
dp[4][4] = 1: the single letter 'b' is a palindrome
s
Row i is where the substring starts and column j where it ends, so only the upper triangle is used. Rows fill from the bottom up. The cell being filled is solid and the cells it read are tinted: the inside on a match, below and left otherwise. Try With gaps to see the answer skip a letter.
Dry Run Table
Input: "cbbd" (indexes 0-3). Rows go from i = 3 up to i = 0.
| i | j | Ends | Calculation | dp[i][j] |
|---|---|---|---|---|
| 3 | 3 | d | one letter | 1 |
| 2 | 2 | b | one letter | 1 |
| 2 | 3 | b, d | max(dp[3][3], dp[2][2]) | 1 |
| 1 | 1 | b | one letter | 1 |
| 1 | 2 | b, b | match, nothing inside: 0 + 2 | 2 |
| 1 | 3 | b, d | max(dp[2][3], dp[1][2]) = max(1, 2) | 2 |
| 0 | 0 | c | one letter | 1 |
| 0 | 1 | c, b | max(dp[1][1], dp[0][0]) | 1 |
| 0 | 2 | c, b | max(dp[1][2], dp[0][1]) = max(2, 1) | 2 |
| 0 | 3 | c, d | max(dp[1][3], dp[0][2]) = max(2, 2) | 2 |
Answer: dp[0][3] = 2, the subsequence "bb".
The Solution Template
An n × n table filled from the last row up, each row from the diagonal to the right.
Longest Palindromic Subsequence Code
1var longestPalindromeSubseq = function(s) {2 const n = s.length;3 const dp = Array.from({ length: n }, () => new Array(n).fill(0));4 for (let i = n - 1; i >= 0; i--) {5 dp[i][i] = 1;6 for (let j = i + 1; j < n; j++) {7 if (s[i] === s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;8 else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);9 }10 }11 return dp[0][n - 1];12};
Edge Cases & Common Mistakes
- One letter: the answer is 1.
- Two equal letters next to each other: the inside is empty;
dp[i+1][j-1]sits below the diagonal and must read as 0. - Wrong fill order: filling rows top-down reads
dp[i+1][...]before it exists. Go fromi = n - 1up, or fill by increasing length. - Confusing it with the substring problem: a subsequence may skip letters, so
"agbdba"gives 5, not 3. - Space: only the row below is ever read, so two 1-D arrays bring space down to O(n).
Summary
dp[i][j] is the answer for s[i..j]. One letter is 1; matching ends give dp[i+1][j-1] + 2; otherwise max(dp[i+1][j], dp[i][j-1]). Fill from the bottom row up and return dp[0][n-1]. O(n²) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet