[Solved] 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.

Question

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.

Python Solution

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        l = len(s)
        matrix = [[0 for _ in range(l)] for _ in range(l)]
        
        for i in range(l):
            matrix[i][i] = 1
        
        for i in range(l-1,-1,-1):
            for j in range(i+1,l):
                if s[i]==s[j]:
                    matrix[i][j] = matrix[i+1][j-1] + 2
                else:
                    matrix[i][j] = max(matrix[i+1][j],matrix[i][j-1])
        
        return matrix[0][-1]