# Longest Palindromic Subsequence

Given a string `s`, find the longest palindromic subsequence's length in `s`.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

```Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".
```

Example 2:

```Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".
```

Constraints:

• `1 <= s.length <= 1000`
• `s` consists only of lowercase English letters.

### Solution(Pythn3) :

Using Top-Down Dynamic Programming:
• Let `dp(l, r)` denote the length of the longest palindromic subsequence of `s[l..r]`.
• There are 2 options:
• If `s[l] == s[r]` then `dp[l][r] = dp[l+1][r-1] + 2`
• Elif `s[l] != s[r]` then `dp[l][r] = max(dp[l+1][r], dp[l][r-1])`.
• Then `dp(0, n-1)` is our result.
```def longestPalindromeSubseq(s: str) -> int:
r = len(s) - 1
cache = {}  # (l, r) longest string = r -l

def dp(l, r):
if l > r:
return 0
if l == r:
return 1
if (l, r) in cache:
return cache[(l, r)]
if s[l] == s[r]:
cache[(l, r)] = 2 + dp(l + 1, r - 1)
else:
cache[(l, r)] = max(dp(l, r - 1), dp(l + 1, r))
return cache[(l, r)]
return dp(0, r)
```

Uk01 on Jan 18, 2022 at 12:01 am

If you like dEexams.com and would like to contribute, you can write your article here or mail your article to admin@deexams.com . See your article appearing on the dEexams.com main page and help others to learn.

×