BinarySearch 0026 Longest Palindromic Subsequence

Problem statement

https://binarysearch.com/problems/Longest-Palindromic-Subsequence/

Solution

Equal to Leetcode 0516 Longest Palindromic Subsequence

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 solve(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))