Maximize Palindrome Length From Subsequences LeetCode solution in Python

1
class Solution:
2
    def longestPalindrome(self, word1: str, word2: str) -> int:
3
        res = 0
4
        new_word = word1 + word2
5
        n, mid = len(word1) + len(word2), len(word1)
6
        dp = [[0] * n for _ in range(n)]
7
        for i in range(n):
8
            dp[i][i] = 1
9
        for l in range(n - 2, -1, -1):
10
            for r in range(l + 1, n, 1):
11
                if new_word[l] == new_word[r]:
12
                    dp[l][r] = (dp[l + 1][r - 1] if r - 1 >= l + 1 else 0) + 2
13
                    if l < mid and r >= mid:
14
                        res = max(res, dp[l][r])
15
                else:
16
                    dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])
17
        return res