两个回文子序列长度的最大乘积 图解题解
这道题到底在问什么
- 输入
- s = "leetcodecom"
- 输出
- 9(选 "ete" 和 "cdc",乘积 3×3)
- 输入
- s = "accbcaxxcxx"
- 输出
- 25(选 "accca" 和 "xxcxx",乘积 5×5)
- 输入
- s = "bb"
- 输出
- 1(两个 "b" 各占一个,乘积 1×1)
先想最直接的笨办法
这一种分法:绿色的下标 0、1、4 组成 A,读作 aba;蓝色的下标 3 组成 B,读作 b;灰色的位置不用。让 A 长一点试试:取下标 0、1、4 组成 aba。（动画第 13 步）
最优解：一步一步想明白
- 3记牢这一句:每个下标要么进 A、要么进 B、要么不用,A 和 B 各自是回文、互不占用同一个下标。把所有分法试一遍,长度乘积最大的那个就是答案。下面用 abcba 这五个字符,一种分法一种分法地走。
- 4先把 s 等于 abcba 摆好,下标从 0 到 4。中间那个 c 只有一个,两端是对称的 a 和 b。绿色代表这个下标进 A 组,蓝色代表进 B 组,灰色代表这一位不用。右边的面板会记下我们试过的每一种分法和它的乘积。现在还没开始,面板是空的。
- 5强调一下规则再动手。abcba 有五个位置,每个位置只能落到一个去处:要么是 A 的一部分,要么是 B 的一部分,要么空着不选。所以两组永远不会抢同一个字符。下面我挑几种有代表性的分法,带你把判断流程走顺,你就明白代码在幕后是怎么把所有分法都扫一遍的。
- 6这一种分法:绿色的下标 0、4 组成 A,读作 aa;蓝色的下标 1、3 组成 B,读作 bb;灰色的位置不用。两端的 a 配 a 做 A,中间的两个 b 做 B,c 不用。
- 7先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[4] 是 a。一路收到中间都对得上,aa 是回文,长度记作 2。
- 8再验 B 组。同样两端往里收,s[1] 是 b,s[3] 是 b。bb 是回文,长度 2,两组都合法,可以算乘积了。
- 9两组都合法。A 长 2,B 长 2,乘积 4。比之前记的最优 还高,把最优刷新成 4。面板里把这条记上。
- 10这一种分法:绿色的下标 0、1 组成 A,读作 ab;蓝色的下标 3、4 组成 B,读作 ba;灰色的位置不用。故意选一组不回文的 A,看看流程怎么把它淘汰。
- 11先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[1] 是 b。这两端就对不上了,ab 不是回文,这种分法直接淘汰,连 B 都不用看了。
- 12A 组不是回文,那不管 B 怎么选,这种分法都不合法,把它标红作废。右边面板记一笔:这条淘汰。当前保持的最优乘积还是 4,接着换下一种分法。
- 13这一种分法:绿色的下标 0、1、4 组成 A,读作 aba;蓝色的下标 3 组成 B,读作 b;灰色的位置不用。让 A 长一点试试:取下标 0、1、4 组成 aba。
- 14先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[4] 是 a。一路收到中间都对得上,aba 是回文,长度记作 3。
- 15再验 B 组。同样两端往里收,s[3] 是 b,s[3] 是 b。b 是回文,长度 1,两组都合法,可以算乘积了。
- 16两组都合法。A 长 3,B 长 1,乘积 3。没有超过已经记下的 4,最优不变。面板里把这条记上。
- 17这一种分法:绿色的下标 0、2、4 组成 A,读作 aca;蓝色的下标 1、3 组成 B,读作 bb;灰色的位置不用。这次让 A 跳过中间取 0、2、4 组成 aca,B 还是两个 b。
- 18先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[4] 是 a。一路收到中间都对得上,aca 是回文,长度记作 3。
- 19再验 B 组。同样两端往里收,s[1] 是 b,s[3] 是 b。bb 是回文,长度 2,两组都合法,可以算乘积了。
- 20两组都合法。A 长 3,B 长 2,乘积 6。比之前记的最优 还高,把最优刷新成 6。面板里把这条记上。
- 21这一种分法:绿色的下标 1、2、3 组成 A,读作 bcb;蓝色的下标 0、4 组成 B,读作 aa;灰色的位置不用。换个对称中心:A 取中间三个 bcb,B 取两端的 aa。
- 22先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[1] 是 b,s[3] 是 b。一路收到中间都对得上,bcb 是回文,长度记作 3。
- 23再验 B 组。同样两端往里收,s[0] 是 a,s[4] 是 a。aa 是回文,长度 2,两组都合法,可以算乘积了。
- 24两组都合法。A 长 3,B 长 2,乘积 6。没有超过已经记下的 6,最优不变。面板里把这条记上。
- 25这一种分法:绿色的下标 0、1、2、3、4 组成 A,读作 abcba;蓝色的下标 暂无 组成 B,读作 空;灰色的位置不用。极端一点:整串 abcba 全给 A,看 B 会怎样。
- 26先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[4] 是 a。一路收到中间都对得上,abcba 是回文,长度记作 5。
- 27A 已经把能用的字符占满了,剩给 B 的是空的。可题目要两个子序列,B 不能是空,长度 0 一乘乘积就是 0,这种分法虽然 A 很长也没意义。
- 28这种分法乘积是 0,对答案没有帮助,略过。当前最优乘积还是 6。
- 29所有代表性的分法都试完了,回放一下赢家。A 取下标 0、2、4 组成 aca,是长度 3 的回文;B 取下标 1、3 组成 bb,是长度 2 的回文;两组不占同一个字符。乘积 3 乘 2 等于 6,这就是最大乘积。面板里这一行正是最高的那个。
- 30再看一眼这个画面:绿色的 aca 和蓝色的 bb 拼在一起正好用掉五个位置,c 归 aca、两个 a 也归 aca、两个 b 归 bb。它俩长度相乘 6,胜过其它所有分法。参考代码做的就是把这种分法穷举一遍,只不过它用位掩码来枚举下标集合,速度更快。
⚠️ 容易写错的地方
✗ 错：以为要在字符串上跑一个复杂的区间动态规划
✓ 对：n 很小,直接位掩码枚举所有子集
约束 n ≤ 12 意味着子集数量 2ⁿ 最多四千多,枚举加判回文完全跑得动,不必套编辑距离那类 DP
✗ 错：把 B 允许取空、算出乘积 0 也去更新答案
✓ 对：要求两个子序列都非空,枚举 j 时从 1 开始、跳过空集
空子序列长度 0,乘积恒为 0,既不合题意也拉不高答案,让 B 非空才是正解
✗ 错：判回文时把没选中的下标也拿去比较
✓ 对：两端指针先跳过没被选中的位,只比选中的字符
子序列只由被选中的下标组成,没选的字符根本不在这个子序列里,比了就判错
✗ 错：让 A 和 B 共用同一个下标
✓ 对：B 只能在 A 的补集里选,保证两组下标不相交
题目要求两个子序列不相交,同一个字符不能算两次长度
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int maxProduct(string s) {
int n = s.size();
vector<bool> p(1 << n, true);
for (int k = 1; k < 1 << n; ++k) {
for (int i = 0, j = n - 1; i < j; ++i, --j) {
while (i < j && !(k >> i & 1)) {
++i;
}
while (i < j && !(k >> j & 1)) {
--j;
}
if (i < j && s[i] != s[j]) {
p[k] = false;
break;
}
}
}
int ans = 0;
for (int i = 1; i < 1 << n; ++i) {
if (p[i]) {
int a = __builtin_popcount(i);
int mx = ((1 << n) - 1) ^ i;
for (int j = mx; j; j = (j - 1) & mx) {
if (p[j]) {
int b = __builtin_popcount(j);
ans = max(ans, a * b);
}
}
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxProduct(String s) {
int n = s.length();
boolean[] p = new boolean[1 << n];
Arrays.fill(p, true);
for (int k = 1; k < 1 << n; ++k) {
for (int i = 0, j = n - 1; i < n; ++i, --j) {
while (i < j && (k >> i & 1) == 0) {
++i;
}
while (i < j && (k >> j & 1) == 0) {
--j;
}
if (i < j && s.charAt(i) != s.charAt(j)) {
p[k] = false;
break;
}
}
}
int ans = 0;
for (int i = 1; i < 1 << n; ++i) {
if (p[i]) {
int a = Integer.bitCount(i);
int mx = ((1 << n) - 1) ^ i;
for (int j = mx; j > 0; j = (j - 1) & mx) {
if (p[j]) {
int b = Integer.bitCount(j);
ans = Math.max(ans, a * b);
}
}
}
}
return ans;
}
}复杂度
时间
O(3ⁿ + 2ⁿ·n)
n 是字符串长度。判回文那步扫 2 的 n 次方个子集、每个子集两端指针走 O(n),是 2ⁿ 乘 n;配对那步对每个子集枚举补集的所有子掩码,所有子集的子掩码总数是 3 的 n 次方。因为 n 最多 12,总量完全可控
空间
O(2ⁿ)
按峰值算。主要开销是记录每个子集是否回文的布尔数组 p,长度 2 的 n 次方。除此之外只用了几个指针和计数变量,是常数级
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两个回文子序列长度的最大乘积 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么敢用指数级的枚举?+
关键在约束 n ≤ 12。子集总数是 2 的 n 次方,最多也就四千多个;判回文那步是 2ⁿ 乘 n,配对枚举子掩码那步所有子集加起来是 3 的 n 次方,n 等于 12 时也就五十多万量级,现代机器毫秒级跑完。约束把规模死死锁住,指数枚举反而是最省心的正解,不需要设计精巧的多项式算法。
判一个子集选出的字符是不是回文,怎么高效做?+
用两端指针 i 和 j,从子集对应的最外层往里收。每一步先让 i 向右跳过没被选中的位、j 向左跳过没被选中的位,让它们都停在真正被选中的字符上,再比较 s[i] 和 s[j]。相等就继续往里收,不等就整个子集不是回文。这样每个子集判一次是 O(n)。
除了枚举补集子掩码,还有别的配对方式吗?+
可以先把所有回文子集连同它们的位掩码和长度收进一个列表,再两两检查掩码按位与是否为 0,为 0 就说明两组下标不相交,可以配对更新乘积。这是另一种可行写法,n 不超过 12 时也跑得动,随机数据下回文子集少时可能更省;但补集子掩码写法更短、常数更小,面试里两种都能说清就够了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 两个回文子序列长度的最大乘积 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。