Longest Palindromic Subsequence
Problem Statement
Given a string s, return the length of the longest palindromic subsequence in s. A subsequence may skip characters, and a palindrome reads the same forward and backward.
Input
A lowercase string s.
Output
An integer: the length of the longest palindromic subsequence.
Constraints
- •
1 <= s.length <= 1000 - •
s consists only of lowercase English letters
Examples
Example 1
s = bbbab
4Example 2
s = cbbd
2Example 3
s = agbdba
5Learning Objectives
- Define an interval DP state over the substring boundaries **i** and **j**.
- Fill interval states in an order that guarantees inner intervals are already known.
- Relate longest palindromic subsequence to LCS between a string and its reverse.
- Differentiate palindromic subsequence from palindromic substring.
Intuition
A palindrome is controlled by its two ends. For a substring from i to j, if s[i] and s[j] match, those two characters can wrap the best palindromic subsequence inside i + 1 to j - 1.
If the ends do not match, they cannot both be used as the outer pair of the same palindrome. The best answer must skip the left end or skip the right end, so take the better of those two smaller intervals.
The length is also equivalent to the LCS of s and reverse(s) because a palindromic subsequence appears in both directions. The interval DP is usually the cleaner explanation for this exact problem, while the LCS view connects it to the previous lesson.
Common mistakes
- ×Solving longest palindromic substring instead of subsequence and requiring contiguous characters.
- ×Filling the table left-to-right by **i** before the inner interval **dp[i + 1][j - 1]** is available.
- ×When ends match, using only 2 and forgetting to add the best inner palindrome.
- ×When ends differ, taking the minimum or diagonal instead of max of skipping one end.
- ×For the LCS formulation, forgetting that the reversed string must preserve order in the opposite direction.
State Definition
Let dp[i][j] be the length of the longest palindromic subsequence contained in the substring from index i through index j, inclusive. The answer is dp[0][n - 1].
State Transition
Every single character is a palindrome, so dp[i][i] = 1.
For a longer interval i..j:
If s[i] == s[j], then dp[i][j] = 2 + dp[i + 1][j - 1]. For length 2, the inner interval is empty and contributes 0.
If s[i] != s[j], then dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
Fill by increasing interval length, or equivalently iterate i from n - 1 down to 0 and j from i + 1 up to n - 1. This ensures the inner, left-skipped, and right-skipped intervals are already computed.
Solutions
Solution 1: Interval DP by substring boundaries
Use this as the primary solution. It directly models the palindrome endpoints and makes the required fill order clear.
Create a square table where each cell answers one substring interval. Fill from shorter intervals to longer intervals by moving the left boundary backward and the right boundary forward. Matching endpoints wrap the inner answer; non-matching endpoints choose the better skip.
Step-by-step
- Let n = s.length and allocate dp[n][n].
- Iterate i from n - 1 down to 0. Set dp[i][i] = 1 for the single-character interval.
- For each i, iterate j from i + 1 to n - 1.
- If the endpoint characters match, store 2 plus the inner interval length.
- Otherwise, store the max of skipping the left endpoint and skipping the right endpoint.
- Return dp[0][n - 1].
O(n^2)
O(n^2)
There are O(n^2) intervals and each is computed in O(1).
Java implementation
Solution 2: LCS with the reversed string
Use this when you have just discussed LCS or want a quick reduction. It is equally valid for the length, though the interval DP usually communicates the palindrome-specific reasoning better.
Reverse s and compute the longest common subsequence between s and that reversed string. The best common-subsequence length matches the longest palindromic subsequence length in the original string.
Step-by-step
- Build reversed with new StringBuilder(s).reverse().toString().
- Run the standard LCS prefix DP between s and reversed.
- A match extends the diagonal; a mismatch skips one side.
- Return the bottom-right LCS length.
O(n^2)
O(n^2)
This is the standard LCS table on two strings of length n.
Java implementation
Dry Run
Sample input
s = bbbab. Trace selected interval states in the order smaller intervals become available before larger intervals.
| interval | substring | transition | dp value |
|---|---|---|---|
| [0,0] | b | single-character base case | 1 |
| [0,1] | bb | ends match, 2 plus empty middle | 2 |
| [1,2] | bb | ends match, 2 plus empty middle | 2 |
| [0,2] | bbb | ends match, 2 + dp[1][1] | 3 |
| [2,4] | bab | ends match, 2 + dp[3][3] | 3 |
| [1,4] | bbab | ends match, 2 + dp[2][3] | 3 |
| [0,4] | bbbab | ends match, 2 + dp[1][3] | 4 |
The full interval [0,4] has value 4, so the longest palindromic subsequence length is 4.
Complexity Analysis
Both interval DP and the LCS reduction run in O(n^2) time and O(n^2) space. The interval form is more direct for explaining endpoint choices.
Interval DP by substring boundaries
O(n^2)
O(n^2)
There are O(n^2) intervals and each is computed in O(1).
LCS with the reversed string
O(n^2)
O(n^2)
This is the standard LCS table on two strings of length n.
Interview Tips
Emphasize fill order. The recurrence is simple, but it only works if dp[i + 1][j - 1], dp[i + 1][j], and dp[i][j - 1] are already known. A strong answer mentions both valid orders: increasing substring length or left index descending with right index ascending.
Likely follow-ups
- Can you reduce the interval DP to O(n) space?
- How would you reconstruct one longest palindromic subsequence?
- How is this different from Longest Palindromic Substring?
- Why does LCS with the reversed string give the same length?
Similar Problems
Key Takeaways
- Interval DP is natural when a decision depends on both ends of a substring.
- Matching ends wrap the best inner palindromic subsequence.
- Non-matching ends force you to skip one side and take the better interval.
- Longest palindromic subsequence is equivalent in length to LCS of the string and its reverse.