Maximize Palindrome Length From Subsequences — LeetCode 1771 Python Solution

The problem

You are given two strings, word1 and word2. You want to construct a string in the following manner: Choose some non-empty subsequence subsequence1 from word1.

Example

Input

word1 = "cacb", word2 = "cbba"

Output

5

Explanation

Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.

Python solution

class Solution:
    def longestPalindrome(self, word1: str, word2: str) -> int:
        s = word1 + word2
        n = len(s)
        f = [[0] * n for _ in range(n)]
        for i in range(n):
            f[i][i] = 1
        ans = 0
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1] + 2
                    if i < len(word1) <= j:
                        ans = max(ans, f[i][j])
                else:
                    f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return ans

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1771. Maximize Palindrome Length From Subsequences is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems