LeetCode 题解工作台
两个回文子序列长度的最大乘积
给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。 请你返回两个回文子序列长度可以达到的 最大乘积 。 子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们注意到，字符串 的长度不超过 ，因此我们可以使用二进制枚举的方法来枚举 的所有子序列。不妨设 的长度为 ，我们可以使用 个长度为 的二进制数来表示 的所有子序列。对于每个二进制数，第 位为 表示 的第 个字符在子序列中，为 表示不在子序列中。我们对于每个二进制数，判断其是否为回文子序列，并且记录在数组 中。 接下来，我们枚举 中的每个数 ，如果 是回文子序列，那么我…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相交 的。
请你返回两个回文子序列长度可以达到的 最大乘积 。
子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符串是一个 回文字符串 。
示例 1：
输入：s = "leetcodecom" 输出：9 解释：最优方案是选择 "ete" 作为第一个子序列，"cdc" 作为第二个子序列。 它们的乘积为 3 * 3 = 9 。
示例 2：
输入：s = "bb" 输出：1 解释：最优方案为选择 "b" （第一个字符）作为第一个子序列，"b" （第二个字符）作为第二个子序列。 它们的乘积为 1 * 1 = 1 。
示例 3：
输入：s = "accbcaxxcxx" 输出：25 解释：最优方案为选择 "accca" 作为第一个子序列，"xxcxx" 作为第二个子序列。 它们的乘积为 5 * 5 = 25 。
提示：
2 <= s.length <= 12s只含有小写英文字母。
解题思路
方法一：二进制枚举
我们注意到，字符串 的长度不超过 ，因此我们可以使用二进制枚举的方法来枚举 的所有子序列。不妨设 的长度为 ，我们可以使用 个长度为 的二进制数来表示 的所有子序列。对于每个二进制数，第 位为 表示 的第 个字符在子序列中，为 表示不在子序列中。我们对于每个二进制数，判断其是否为回文子序列，并且记录在数组 中。
接下来，我们枚举 中的每个数 ，如果 是回文子序列，那么我们可以从 的补集 中枚举一个数 ，如果 也是回文子序列，那么 和 就是我们要找的两个回文子序列，它们的长度分别为 和 的二进制表示中的 的个数，我们记为 和 ，那么它们的乘积就是 ，我们取所有可能的 中的最大值即可。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
p = [True] * (1 << n)
for k in range(1, 1 << n):
i, j = 0, n - 1
while i < j:
while i < j and (k >> i & 1) == 0:
i += 1
while i < j and (k >> j & 1) == 0:
j -= 1
if i < j and s[i] != s[j]:
p[k] = False
break
i, j = i + 1, j - 1
ans = 0
for i in range(1, 1 << n):
if p[i]:
mx = ((1 << n) - 1) ^ i
j = mx
a = i.bit_count()
while j:
if p[j]:
b = j.bit_count()
ans = max(ans, a * b)
j = (j - 1) & mx
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(2^n * 2^n * n) in the worst case due to enumerating all subsequence pairs and checking palindromes of length n. Space complexity is O(2^n * n) to store palindrome lengths for each subsequence mask. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can you generate all subsequences and efficiently check for palindromes?
- question_mark
Consider bitmasking to represent subsequences and check disjoint characters quickly.
- question_mark
Can you optimize by storing palindromic lengths to avoid repeated computation?
常见陷阱
外企场景- error
Failing to ensure the two subsequences are disjoint by index.
- error
Rechecking palindrome property repeatedly instead of caching results.
- error
Overlooking subsequences that maximize product due to greedy selection of longest palindromes first.
进阶变体
外企场景- arrow_right_alt
Find the maximum sum of lengths instead of product for two disjoint palindromic subsequences.
- arrow_right_alt
Allow three disjoint palindromic subsequences and maximize the product of their lengths.
- arrow_right_alt
Restrict subsequences to a specific minimum length and compute the maximum product.