Given a string s, return the length of its longest palindromic subsequence. A subsequence keeps the original order of characters but may skip some of them; it does not have to be contiguous.
- 1 <= s.length <= 1000
- `s` has only lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force lists all 2^n subsequences and checks each one. Instead, think about the substring s[i..j]. State: dp[i][j] is the length of the longest palindromic subsequence inside s[i..j]. Recurrence: if s[i] == s[j], both ends wrap around the best answer inside, so dp[i][j] = dp[i+1][j-1] + 2. Otherwise one of the ends is not used, so dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Base case: a single character is a palindrome, dp[i][i] = 1, and an empty range is 0. Row i depends only on row i+1, so two 1D arrays are enough.
Algorithm
- Keep
prevfor rowi+1and buildcurfor rowi, withigoing fromn-1down to 0. - Set
cur[i] = 1. - For
jfromi+1ton-1: ifs[i] == s[j],cur[j] = prev[j-1] + 2, elsecur[j] = max(prev[j], cur[j-1]). - After the row, set
prev = cur. - Return
prev[n-1], which isdp[0][n-1].
O(n^2)Space: O(n)s and its reverse. Also, "minimum deletions to make a palindrome" is just n minus this answer.class Solution: def longestPalindromeSubseq(self, s: str) -> int: n = len(s) prev = [0] * n # dp row i + 1 for i in range(n - 1, -1, -1): cur = [0] * n # dp row i cur[i] = 1 for j in range(i + 1, n): if s[i] == s[j]: cur[j] = prev[j - 1] + 2 else: cur[j] = max(prev[j], cur[j - 1]) prev = cur return prev[n - 1]