Longest Palindromic Subsequence . dEexams.com

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.