Leetcode 0516 Longest Palindromic Subsequence

Problem statement

https://leetcode.com/problems/longest-palindromic-subsequence/

Solution

Let us define by dp[i][j] the maximum length of palindromic sub-sequence for s[i:j+1]. Then we need to look at dp[i][j-1], dp[i+1][j] and to dp[i+1][j-1] if s[i] == s[j].

Complexity

Time complexity will be O(n^2), space complexity is O(n^2), which can be reduced to O(n).

Code

class Solution:
    def longestPalindromeSubseq(self, s):
        @lru_cache(None)
        def dp(i, j):
            if j - i <= 1: return j - i
            if s[i] == s[j-1]: 
                return dp(i + 1, j - 1) + 2
            else:
                return max(dp(i, j-1), dp(i + 1, j))
                
        return dp(0, len(s))