题目描述
思路解析
一句话答案：LeetCode 2002 两个回文子序列长度的最大乘积：n≤12 让指数枚举成为正解，位掩码枚举每个下标子集、预判是否回文，再对补集枚举子掩码配对，两组下标不共用，取乘积最大，时间 O(3ⁿ+2ⁿ·n)、空间 O(2ⁿ)。
两个回文子序列不相交，到底在挑什么
从 s 里挑两个子序列（删掉若干字符、剩下保持原顺序），各自是回文（正读反读一样），互不相交——同一个下标不能两边都用，求长度乘积最大。题面 leetcodecom 里 ete（下标 1、3、7）配 cdc（4、6、8），零重叠，3×3=9。s 长度顶多 12，是整道题的方向盘。
先抢一条最长回文，为什么会亏
先拿一条最长回文、剩下再取第二条，在题面 accbcaxxcxx 上露馅：长 5 的最长回文不止一条——取 accca，剩下恰好凑出 xxcxx，5×5=25；取 ccbcc 就抢走了 xxcxx 中间那个 c，最多剩 xxxx，5×4=20。
每个下标三个去处（进第一条、进第二条、不用），3¹²≈53 万种分法，机器一眨眼；别硬套 DP（动态规划，把「区间内最长回文多长」存表复用，这题数得完，用不上），枚举就是正解。
选了哪些下标，怎么塞进一个整数里
用位掩码记「选了哪些下标」：整数二进制第 i 位是 1 表示选中下标 i，掩码最右一位对应下标 0，4095 个掩码（n=12 时从 1 数到 2¹²−1=4095）扫遍全部非空子集，这套压法就是状态压缩。两件事变简单：m1 & m2 == 0（没有一位同时是 1）就是两组下标不共用；掩码里 1 的个数就是子序列长度。
参考代码先开布尔表 p，对每个掩码 k 用两端指针验回文：为 0 的位直接跳过，撞上 s[i] != s[j] 就记 p[k] = False。
第二条为什么只能去补集里挑
对每个回文掩码 i，第二条只从补集 mx = ((1 << n) - 1) ^ i（1<<n 是把 1 左移 n 位；(1<<n)−1 就是 n 位全 1；^ 是异或——把 i 里是 1 的位翻成 0，得到补集）里挑：从中选的子掩码天然不和 i 相交。枚举从 j = mx 开始，每步 j = (j - 1) & mx，把减 1 后越出补集的位掐掉，不重不漏扫完全部子集，p[j] 为真就拿两边 1 的个数相乘更新答案。
bb 的三个掩码各自长什么样
题面 s = bb 只有三个掩码：01 选出单个 b，单字符自然回文，p[01] 为真；10 同理；11 选出 bb，两端都是 b，也为真。
配对：第一条取 01 时补集 mx=10，j 从 10 起步，p[10] 为真，1×1=1 记进答案；再走 j=(10-1)&10=00 结束。第一条取 10 时补集是 01，同样得 1。取 11 时补集是 00：整串占满，另一条只能空着。答案 1，对上题面。
子掩码枚举漏了与上 mx，会把哪些非法配对数进来
把 j = (j - 1) & mx 写成裸的 j = j - 1，会把和 i 抢下标的掩码也数进候选，答案跟着变大。空集天然被挡在外：j 从 mx 起步、条件 j 非零；n≥2 时答案至少 1，两个单字符各占一位就是一对。
验回文一步扫 2ⁿ 个掩码、每个指针走 O(n)（大 O，衡量数据变大时操作量怎么涨）；配对的子掩码总数是 3ⁿ，还是三个去处那笔账。合计 O(3ⁿ + 2ⁿ·n)，空间是布尔表 O(2ⁿ)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:每个下标要么进 A、要么进 B、要么不用,A 和 B 各自是回文、互不占用同一个下标。把所有分法试一遍,长度乘积最大的那个就是答案。下面用 abcba 这五个字符,一种分法一种分法地走。
先把 s 等于 abcba 摆好,下标从 0 到 4。中间那个 c 只有一个,两端是对称的 a 和 b。绿色代表这个下标进 A 组,蓝色代表进 B 组,灰色代表这一位不用。右边的面板会记下我们试过的每一种分法和它的乘积。现在还没开始,面板是空的。
强调一下规则再动手。abcba 有五个位置,每个位置只能落到一个去处:要么是 A 的一部分,要么是 B 的一部分,要么空着不选。所以两组永远不会抢同一个字符。下面我挑几种有代表性的分法,带你把判断流程走顺,你就明白代码在幕后是怎么把所有分法都扫一遍的。
这一种分法:绿色的下标 0、4 组成 A,读作 aa;蓝色的下标 1、3 组成 B,读作 bb;灰色的位置不用。两端的 a 配 a 做 A,中间的两个 b 做 B,c 不用。
先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[4] 是 a。一路收到中间都对得上,aa 是回文,长度记作 2。
再验 B 组。同样两端往里收,s[1] 是 b,s[3] 是 b。bb 是回文,长度 2,两组都合法,可以算乘积了。
两组都合法。A 长 2,B 长 2,乘积 4。比之前记的最优 还高,把最优刷新成 4。面板里把这条记上。
这一种分法:绿色的下标 0、1 组成 A,读作 ab;蓝色的下标 3、4 组成 B,读作 ba;灰色的位置不用。故意选一组不回文的 A,看看流程怎么把它淘汰。
先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[1] 是 b。这两端就对不上了,ab 不是回文,这种分法直接淘汰,连 B 都不用看了。
A 组不是回文,那不管 B 怎么选,这种分法都不合法,把它标红作废。右边面板记一笔:这条淘汰。当前保持的最优乘积还是 4,接着换下一种分法。
这一种分法:绿色的下标 0、1、4 组成 A,读作 aba;蓝色的下标 3 组成 B,读作 b;灰色的位置不用。让 A 长一点试试:取下标 0、1、4 组成 aba。
先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[4] 是 a。一路收到中间都对得上,aba 是回文,长度记作 3。
再验 B 组。同样两端往里收,s[3] 是 b,s[3] 是 b。b 是回文,长度 1,两组都合法,可以算乘积了。
两组都合法。A 长 3,B 长 1,乘积 3。没有超过已经记下的 4,最优不变。面板里把这条记上。
这一种分法:绿色的下标 0、2、4 组成 A,读作 aca;蓝色的下标 1、3 组成 B,读作 bb;灰色的位置不用。这次让 A 跳过中间取 0、2、4 组成 aca,B 还是两个 b。
先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[4] 是 a。一路收到中间都对得上,aca 是回文,长度记作 3。
再验 B 组。同样两端往里收,s[1] 是 b,s[3] 是 b。bb 是回文,长度 2,两组都合法,可以算乘积了。
两组都合法。A 长 3,B 长 2,乘积 6。比之前记的最优 还高,把最优刷新成 6。面板里把这条记上。
这一种分法:绿色的下标 1、2、3 组成 A,读作 bcb;蓝色的下标 0、4 组成 B,读作 aa;灰色的位置不用。换个对称中心:A 取中间三个 bcb,B 取两端的 aa。
先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[1] 是 b,s[3] 是 b。一路收到中间都对得上,bcb 是回文,长度记作 3。
再验 B 组。同样两端往里收,s[0] 是 a,s[4] 是 a。aa 是回文,长度 2,两组都合法,可以算乘积了。
两组都合法。A 长 3,B 长 2,乘积 6。没有超过已经记下的 6,最优不变。面板里把这条记上。
这一种分法:绿色的下标 0、1、2、3、4 组成 A,读作 abcba;蓝色的下标 暂无 组成 B,读作 空;灰色的位置不用。极端一点:整串 abcba 全给 A,看 B 会怎样。
先验 A 组是不是回文。用两个指针从 A 的两端往中间收,先比最外层:s[0] 是 a,s[4] 是 a。一路收到中间都对得上,abcba 是回文,长度记作 5。
A 已经把能用的字符占满了,剩给 B 的是空的。可题目要两个子序列,B 不能是空,长度 0 一乘乘积就是 0,这种分法虽然 A 很长也没意义。
这种分法乘积是 0,对答案没有帮助,略过。当前最优乘积还是 6。
所有代表性的分法都试完了,回放一下赢家。A 取下标 0、2、4 组成 aca,是长度 3 的回文;B 取下标 1、3 组成 bb,是长度 2 的回文;两组不占同一个字符。乘积 3 乘 2 等于 6,这就是最大乘积。面板里这一行正是最高的那个。
再看一眼这个画面:绿色的 aca 和蓝色的 bb 拼在一起正好用掉五个位置,c 归 aca、两个 a 也归 aca、两个 b 归 bb。它俩长度相乘 6,胜过其它所有分法。参考代码做的就是把这种分法穷举一遍,只不过它用位掩码来枚举下标集合,速度更快。
边界想清:单个字符也是回文,所以最短情况下也能各取一个字符凑出乘积 1;字符越多、越对称,越能拼出更长的两组。
面试重点:n ≤ 12 让指数枚举变成正解、两端指针跳过未选位判回文、配对可枚举补集子掩码或对回文子集两两按位与判不相交。
参考代码
from __future__ import annotationsfrom 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 ans复杂度
- 时间：O(3ⁿ + 2ⁿ·n)，n 是字符串长度。判回文那步扫 2 的 n 次方个子集、每个子集两端指针走 O(n),是 2ⁿ 乘 n;配对那步对每个子集枚举补集的所有子掩码,所有子集的子掩码总数是 3 的 n 次方。因为 n 最多 12,总量完全可控
- 空间：O(2ⁿ)，按峰值算。主要开销是记录每个子集是否回文的布尔数组 p,长度 2 的 n 次方。除此之外只用了几个指针和计数变量,是常数级
易错点
面试追问把动画讲成自己的话
追问这题为什么敢用指数级的枚举?
追问判一个子集选出的字符是不是回文,怎么高效做?
追问除了枚举补集子掩码,还有别的配对方式吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
出租车的最大盈利
LeetCode 2008 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题