#516
Longest Palindromic Subsequence
Medium Interval DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the length of the longest subsequence of s that is a palindrome.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest palindrome you can get by deleting letters.
Why this works: dp[i][j] for s[i..j]: equal ends → 2 + inside; otherwise the better of dropping one end.
Example: "bbbab"
"bbbb" → 4✦Hints open one at a time
dp[i][j] = answer for s[i..j].
If s[i] == s[j], dp[i][j] = dp[i+1][j−1] + 2; else max(dp[i+1][j], dp[i][j−1]).
Fill i from the end so dp[i+1][…] is ready. (It's also LCS of s and reverse(s).)
↗Approach
Single characters are length 1. Loop i from n − 1 down to 0 and j from i + 1 up to n − 1, applying the transition.
</>Solution (Java)
class Solution {
public 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; // both ends used
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
}!Common mistake
Filling i in increasing order, which reads cells that aren't computed yet.
Complexity
- Time: O(n²).
- Space: O(n²).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon