516. Longest Palindromic Subsequence

Idea

I re-visited this problem because of another hard problem (1312), and I found that this problem deserves a post on its own.

We’re trying to find the longest palindromic subsequence, there are few ways to solve subsequence problems and probably the first one we should consider is Dynamic Programming(DP).

DP State

We want the longest, so we start from index 0 and index len-1, and takes them if they are the same, do something else if not, so we need to keep track of two indices, left and right.

So two states l,r.

DP base case

A single char is palindromic -> l==r -> return 1

An empty string is not palindromic -> l>r -> return 0 (left pointer goes beyond right pointer)

DP transition

If the two chars pointed by the two pointers are the same, we have to take them to achieve longest palindromic subsequence, by doing this, the length is increased by 2. -> 2+dp(l+1,r-1)

If the two chars are not the same, we either skip the left one or the right one, then take the larger result. -> max(dp(l+1,r),dp(l,r-1))

Algorithm

Everything is ready now.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        @functools.cache
        def dp(l,r):
            if l==r:
                return 1
            if l>r:
                return 0
            if s[l]==s[r]:
                return 2+dp(l+1,r-1)
            return max(dp(l+1,r),dp(l,r-1))
        return dp(0,len(s)-1)