DP — Longest Palindromic Subsequence
↗ LeetCode: Longest Palindromic Subsequence · Medium · pattern chapter →
Asked atAmazonGoogleMeta
Length of longest palindromic subsequence.
Example 1 — s="bbbab" → 4Example 2 — s="cbbd" → 2
Constraints — 1 ≤ n ≤ 1000. Brute enumerates 2ⁿ subsequences — at n=10³ that's 10³⁰¹ ops (universe-age × 10²⁸⁰). 2D interval DP is O(n²) = 10⁶ ops = ~5 ms.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — LCS(s, reverse(s))
O(n²) — quick way.
Approach 2 — Interval DP (canonical)
Insight. dp[i][j] = LPS length in s[i..j].
java
int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][n-1];
}Execution Trace
Step 1 / 3Initialize scan.
Corollary. Min insertions to make s palindrome = n - LPS(s).
Complexity — Time O(n²); Space O(n²).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| LCS(s, rev) | O(n²) | O(n²) | works |
| Interval DP | O(n²) | O(n²) | canonical |
When to use which
- Standard LPS → interval DP.
- Min insertions to palindrome → same DP.
- Longest palindromic substring → different — see Longest Palindromic Substring.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems