Try it here
Subscribe
Leetcode Palindromes Problem

Longest Palindromic Subsequence

_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)

Writer profile pic

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.



Post Comment

Comments( 0)

×

Forgot Password

Please enter your email address below and we will send you information to change your password.