BinarySearch 0991 Longest Palindrome From Concatenating Two Subsequences

Problem statement

https://binarysearch.com/problems/Longest-Palindrome-From-Concatenating-Two-Subsequences/

Solution

Equal to Leetcode 1771. Maximize Palindrome Length From Subsequences.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, word1, word2):
        m, n, s, ans = len(word1), len(word2), word1 + word2, 0
        
        @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))
                    
        for i, j in product(range(m), range(m + 1, m + n + 1)):
            if s[i] == s[j - 1]:
                ans = max(ans, dp(i, j))
                
        return ans