Problem statement

https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/

Solution

Merge strings and then use dp to find the longest palindrome. Also we look only at those pairs, where the first element from the first part and second from the second.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def longestPalindrome(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