题目描述
思路解析动画文字版
记牢这一句:每个下标要么进 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题