How do I approach solving Maximize Palindrome Length From Subsequences?

Start by understanding the state transition dynamic programming approach, and then optimize for both time and space complexity when handling large input sizes.

What are the key components of the solution for this problem?

The key components are dynamic programming, state transition, and optimization for both time and space complexity.

Why is state transition dynamic programming used here?

State transition dynamic programming allows for exploring all possible subsequences while optimizing for the longest palindromic subsequence.

Can the problem be solved with a greedy algorithm?

No, a greedy approach will not work effectively due to the need to explore all subsequences and their possible combinations.

How can I optimize my solution for larger inputs?

Optimize your solution by reducing space complexity, using techniques like space compression in dynamic programming.

#1771

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

由子序列构造的最长回文串的长度

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：从 word1 中选出某个非空子序列 subsequence1 。从 word2 中选出某个非空子序列 subsequence2 。连接两个子序列 subsequence1 + subsequence2 ，得到…

字符串动态规划

题目描述

给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：

从 word1 中选出某个非空子序列 subsequence1 。
从 word2 中选出某个非空子序列 subsequence2 。
连接两个子序列 subsequence1 + subsequence2 ，得到字符串。

返回可按上述方法构造的最长 回文串 的长度。如果无法构造回文串，返回 0 。

字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。

回文串 是正着读和反着读结果一致的字符串。

示例 1：

输入：word1 = "cacb", word2 = "cbba"
输出：5
解释：从 word1 中选出 "ab" ，从 word2 中选出 "cba" ，得到回文串 "abcba" 。

示例 2：

输入：word1 = "ab", word2 = "ab"
输出：3
解释：从 word1 中选出 "ab" ，从 word2 中选出 "a" ，得到回文串 "aba" 。

示例 3：

输入：word1 = "aa", word2 = "bb"
输出：0
解释：无法按题面所述方法构造回文串，所以返回 0 。

提示：

1 <= word1.length, word2.length <= 1000
word1 和 word2 由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

我们首先将字符串 word1 和 word2 连接起来，得到字符串 $s$ ，然后我们可以将问题转化为求字符串 $s$ 的最长回文子序列的长度。只不过这里在算最后的答案时，需要保证回文字符串中，至少有一个字符来自 word1，另一个字符来自 word2。

我们定义 $f[i][j]$ 表示字符串 $s$ 中下标范围在 $[i, j]$ 内的子串的最长回文子序列的长度。

如果 $s[i] = s[j]$ ，那么 $s[i]$ 和 $s[j]$ 一定在最长回文子序列中，此时 $f[i][j] = f[i + 1][j - 1] + 2$ ，这时候我们还需要判断 $s[i]$ 和 $s[j]$ 是否来自 word1 和 word2，如果是，我们将答案的最大值更新为 $ans=\max(ans, f[i][j])$ 。

如果 $s[i] \neq s[j]$ ，那么 $s[i]$ 和 $s[j]$ 一定不会同时出现在最长回文子序列中，此时 $f[i][j] = max(f[i + 1][j], f[i][j - 1])$ 。

最后我们返回答案即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ ，其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding of dynamic programming and state transitions.
question_mark
Ability to optimize algorithms for handling large input sizes.
question_mark
Proficiency in working with palindromic subsequences in dynamic programming.

warning

常见陷阱

外企场景

error
Misunderstanding the problem by trying to form a palindrome directly from both strings, instead of finding subsequences.
error
Not properly optimizing the space complexity for large inputs.
error
Overcomplicating the dynamic programming state transitions, leading to inefficient solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Different constraints on the lengths of the strings, making optimization more important.
arrow_right_alt
Incorporating constraints on specific characters, affecting subsequence formation.
arrow_right_alt
Adapting the problem to allow for specific subsequence combinations instead of just palindromes.

help

常见问题

外企场景

继续练习

#1745 分割回文串 IV #1871 跳跃游戏 VII #1668 最大重复子字符串