LeetCode 1930 Unique Length-3 Palindromic Subsequences 七种解法全解:从暴力递归到位掩码优化的完整思维链
LeetCode 1930 Unique Length-3 Palindromic Subsequences 七种解法全解:从暴力递归到位掩码优化的完整思维链
本篇技术指南以 LeetCode 1930「Unique Length-3 Palindromic Subsequences」(唯一长度为 3 的回文子序列)为核心,完整讲解从 暴力递归到 位掩码优化的七种解法,并对照本仓库(Leetcode solutions)中 8 种编程语言的实际实现给出源码级佐证。读完本文,你将掌握"子序列枚举去重""首尾索引定界""前缀计数区间查询""位掩码替代集合"四类核心技巧,并能独立推导出该题的最优解及其复杂度边界。
题目回顾与核心观察
给定一个字符串 s,要求返回 所有长度为 3 的不同回文子序列 的数量。例如 s = "aabca",长度为 3 的回文子序列有 "aba"(下标 0,1,3)、"aaa"(下标 0,1,4)、"aca"(下标 0,2,3)与 "aba"(下标 0,2,4)——其中 "aba" 出现两次,只能计一次,最终答案为 3。
本题有几个决定解法的关键性质:
- 回文形式固定:长度为 3 的回文必然形如
aba,即首尾字符相同、中间任意。这是所有解法的出发点。 - 子序列 ≠ 子串:三个字符不必连续,只要保持相对顺序即可。
- 字符集极小:
s仅含 26 个小写字母,因此所有长度为 3 的不同回文子序列至多只有 种(26 种首尾字符 × 26 种中间字符)。这个上界m = 676反复出现在复杂度分析中。
围绕这三点,可以从"生成候选"与"统计存在性"两个角度派生出七种复杂度迥异的解法,下面的章节逐一展开。
前置知识(Prerequisites)
在动手实现前,需要具备以下基础能力:
- Hash Set(哈希集合):用于记录唯一回文子序列、避免重复计数,是解法 1、2、4、6 的核心数据结构;
- String Traversal(字符串遍历):按索引访问字符、维护左右扫描指针;
- Prefix Sum(前缀和,用于最优解):预计算各字符的出现次数,从而 查询任意区间的字符分布(解法 5);
- Bit Manipulation(位运算,用于最优解):用 26 位整数掩码表示"某字符是否出现过",实现 空间的去重(解法 7)。
解法一:递归暴力(Recursion)
直觉
既然长度为 3 的回文形如 aba,我们可以用递归生成所有长度为 3 的子序列,再筛选出回文。每一步对当前字符只有两种选择:跳过或纳入,从而穷举全部 种组合。
算法步骤
- 用集合
res存储找到的唯一回文子序列。 - 定义递归函数
rec(i, cur),i为当前扫描到的下标,cur为正在构造的子序列。 - 若
cur长度达到 3:判断cur[0] == cur[2],成立则加入res,随后返回。 - 若
i到达字符串末尾,直接返回。 - 产生两个递归分支:跳过
s[i](rec(i+1, cur))或纳入s[i](rec(i+1, cur + s[i]))。 - 从
rec(0, "")开始,最终返回len(res)。
以 Python 为例:
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
res = set()
def rec(i, cur):
if len(cur) == 3:
if cur[0] == cur[2]:
res.add(cur)
return
if i == len(s):
return
rec(i + 1, cur)
rec(i + 1, cur + s[i])
rec(0, "")
return len(res)
复杂度
- 时间复杂度:——每个字符都有"选/不选"两个分支;
- 空间复杂度:——递归栈深度 ,加上去重集合最多 个字符串。
其中 为字符串
s的长度, 为唯一长度为 3 的回文子序列数量上限()。
该解法思路最直白,但面对 可达 量级的输入必然超时,仅用于理解问题本质。
解法二:三重循环暴力(Brute Force)
直觉
不生成所有子序列,而是用三层嵌套循环直接枚举三个字符的下标三元组 ,检查 s[i] == s[k] 是否成立。集合保证每个唯一回文只计一次。
算法步骤
- 用集合
res存储唯一回文子序列。 - 枚举
i从0到n-3,j从i+1到n-2,k从j+1到n-1。 - 若
s[i] == s[k],将字符串s[i] + s[j] + s[k]加入res。 - 返回
len(res)。
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
res = set()
for i in range(len(s) - 2):
for j in range(i + 1, len(s) - 1):
for k in range(j + 1, len(s)):
if s[i] != s[k]:
continue
res.add(s[i] + s[j] + s[k])
return len(res)
复杂度
- 时间复杂度:;
- 空间复杂度:。
为字符串长度, 为唯一长度为 3 的回文子序列数量上限(676)。
三层循环虽然避免了递归开销,但 的代价在数据规模稍大时依然不可接受,适合作为对照基线。
解法三:顺序匹配枚举全部回文(Sequential Matching)
直觉
观察上界:候选回文总共只有 个。既然如此,不如反过来——枚举所有候选回文 ends + mid + ends,对每个候选在字符串中做一次顺序匹配(类似子序列判定),能匹配上就计数。匹配的复杂度为 ,总代价为 。
算法步骤
- 初始化
res = 0。 - 外层枚举首尾字符
ends(a 到 z),内层枚举中间字符mid(a 到 z)。 - 构造序列
seq = ends + mid + ends。 - 用一个游标
idx顺序扫描s:每当s中字符等于seq[idx]就推进idx;当idx到达 3 说明匹配成功,res加 1 并跳出。 - 返回
res。
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
res = 0
for ends in range(ord('a'), ord('z') + 1):
for mid in range(ord('a'), ord('z') + 1):
seq = chr(ends) + chr(mid) + chr(ends)
idx, found = 0, 0
for c in s:
if seq[idx] == c:
idx += 1
if idx == 3:
found = 1
break
res += found
return res
复杂度
- 时间复杂度:,其中 为候选回文总数;
- 空间复杂度:,仅使用常数级变量。
为字符串长度, 为唯一长度为 3 的回文子序列数量上限()。
这是"枚举候选 + 判定存在"思想的直接体现,常数因子 676 使其在 时约执行 次基本操作,属于可接受的折中方案。
解法四:遍历中间字符(Iterate On Middle Characters)
直觉
前几种解法要么枚举三元组、要么枚举候选,都是"以两端为中心"。换个视角:以中间字符为中心。回文 x m x 存在,当且仅当字符 x 同时出现在中间字符 m 的左侧与右侧。于是只需遍历每个位置作为中间字符,维护"左侧已见字符集合"与"右侧剩余字符频率",统计两侧交集即可。
算法步骤
- 统计
s中每个字符的总频率(代表初始的"右侧"字符分布)。 - 维护"左侧已见字符"集合
left(初始为空)。 - 用集合
res存储(中间字符, 两端字符)二元组以去重。 - 遍历每个
s[i]:- 先在右侧频率中把
s[i]减一(若减到 0 则移除,表示右侧不再有该字符); - 遍历 26 个字母
c,若c同时出现在left与右侧频率中,说明c + s[i] + c是有效回文,加入res; - 把
s[i]加入left。
- 先在右侧频率中把
- 返回
len(res)。
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
res = set()
left = set()
right = collections.Counter(s)
for i in range(len(s)):
right[s[i]] -= 1
if right[s[i]] == 0:
right.pop(s[i])
for j in range(26):
c = chr(ord('a') + j)
if c in left and c in right:
res.add((s[i], c))
left.add(s[i])
return len(res)
仓库中的 java/1930-unique-length-3-palindromic-subsequences.java 采用的正是这一思路的完整实现:用 Map<Character, Integer> right 维护右侧频率、Set<Character> left 维护左侧字符,并注意在频率归零时 right.remove(c),随后对 26 个字母逐一检查 left.contains(letters[i]) && right.containsKey(letters[i])。
复杂度
- 时间复杂度:,每步最多检查 26 个字母;
- 空间复杂度:,
res最多容纳 676 个二元组。
为字符串长度, 为唯一长度为 3 的回文子序列数量上限(676)。
这一解法将问题从"枚举"降为"单次线性扫描",是理解最优解的关键过渡。
解法五:前缀计数(Prefix Count)
直觉
回文 c ... x ... c 存在,等价于:字符 c 至少出现两次(取首次 l 与末次 r),且在区间 (l, r) 内存在某个字符 x。若我们能 回答"区间 (l, r) 内是否出现字符 x",就能以 完成对每个 c 的统计。前缀计数数组正是为此服务的:prefix[i][c] 表示 s[0..i-1] 中字符 c 的出现次数,任意区间 (l, r) 的计数差 prefix[r][c] - prefix[l+1][c] 即可 求得。
算法步骤
- 构建前缀计数数组
prefix[i][c]=s[0..i-1]中字符c的数量。 - 同时记录每个字符的首次下标
firstIndex与末次下标lastIndex。 - 对每个出现至少两次的字符(
firstIndex != lastIndex):- 令
l = firstIndex,r = lastIndex; - 对 26 个候选中间字符
mid,若prefix[r][mid] - prefix[l+1][mid] > 0,说明区间内存在该字符,答案加 1。
- 令
- 返回总数。
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
n = len(s)
prefix = [[0] * 26 for _ in range(n + 1)]
firstIndex = [-1] * 26
lastIndex = [-1] * 26
for i in range(n):
j = ord(s[i]) - ord('a')
if firstIndex[j] == -1:
firstIndex[j] = i
lastIndex[j] = i
prefix[i + 1] = prefix[i][:]
prefix[i + 1][j] += 1
res = 0
for ends in range(26):
if firstIndex[ends] == -1 or firstIndex[ends] == lastIndex[ends]:
continue
l, r = firstIndex[ends], lastIndex[ends]
for mid in range(26):
if prefix[r][mid] - prefix[l + 1][mid] > 0:
res += 1
return res
复杂度
- 时间复杂度:——构建前缀表 ,统计阶段 次 查询;
- 空间复杂度:——二维前缀表。
前缀计数是"区间统计"类问题的通用武器,代价是 的空间。接下来两种解法会在不牺牲时间的前提下把空间压回 。
解法六:首尾索引 + 集合(First And Last Index)
直觉
回文两端字符必须相同且至少出现两次。对每个字符 c,能够作为中间字符的,必然是首次出现与末次出现之间的某个字符。因此只需定位 c 的首末下标 l、r,把 s[l+1 .. r-1] 中的不同字符个数累加即可——这些不同字符每个都能与两端 c 组成一个唯一回文 c x c。
算法步骤
- 对字符
c(a 到 z):- 用
find/rfind(或indexOf/lastIndexOf)求出l、r; - 若
c未出现或只出现一次(l == -1或l == r),跳过; - 将区间
(l+1, r-1)内的字符收集进集合mids; res += len(mids)。
- 用
- 返回
res。
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
res = 0
for i in range(26):
c = chr(ord('a') + i)
l, r = s.find(c), s.rfind(c)
if l == -1 or l == r:
continue
mids = set()
for j in range(l + 1, r):
mids.add(s[j])
res += len(mids)
return res
仓库中的 python/1930-unique-length-3-palindromic-subsequences.py 是该解法的高度浓缩版:
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
count = 0
chars = set(s)
for char in chars:
first, last = s.find(char), s.rfind(char)
count += len(set(s[first + 1:last]))
return count
先对 set(s) 去重得到候选两端字符,再以切片 + 集合长度直接完成区间不同字符计数,代码仅 7 行。java/1930-unique-length-3-palindromic-subsequences.java 的注释部分也附带了同一思路的 indexOf / lastIndexOf 版本,可作为对照。
复杂度
- 时间复杂度:——对 26 个字符各做一次区间扫描;
- 空间复杂度:——集合
mids最多容纳 26 个不同字符。
由于最多只有 26 个不同字符,
mids规模有常数上界,因此空间可视为 。
解法七:首尾索引 + 位掩码(First And Last Index, Optimal)
直觉
解法六的集合去重有常数开销。既然中间字符只有 26 种,完全可以用一个 26 位整数位掩码 表示"哪些字符已在区间内出现过":第 c 位为 1 表示字符 c 已计入。判断 mask & (1 << c) 是否为 0 即可 判重,置位 mask |= (1 << c) 即可标记。这是位运算替代集合的经典技巧。
算法步骤
- 第一遍扫描:记录每个字符的
firstIndex与lastIndex。 - 对每个至少出现两次的字符:
- 令
l = firstIndex,r = lastIndex; - 初始化
mask = 0; - 遍历
i从l+1到r-1:若mask & (1 << c)为 0,则置位并让结果加 1。
- 令
- 返回总数。
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
firstIndex = [-1] * 26
lastIndex = [-1] * 26
for i in range(len(s)):
j = ord(s[i]) - ord('a')
if firstIndex[j] == -1:
firstIndex[j] = i
lastIndex[j] = i
res = 0
for ends in range(26):
if firstIndex[ends] == -1 or firstIndex[ends] == lastIndex[ends]:
continue
l, r = firstIndex[ends], lastIndex[ends]
mask = 0
for i in range(l + 1, r):
c = ord(s[i]) - ord('a')
if mask & (1 << c):
continue
mask |= (1 << c)
res += 1
return res
复杂度
- 时间复杂度:——两遍线性扫描,内层位运算均为 ;
- 空间复杂度:——仅两个长度 26 的索引数组与一个整数掩码。
由于最多只有 26 个不同字符,辅助空间有常数上界,因此空间为 。
该解法同时满足"时间线性、空间常数"两个目标,是面试与竞赛场景下的推荐实现。仓库中 cpp/1930-unique-length-3-palindromic-subsequences.cpp、rust/1930-unique-length-3-palindromic-subsequences.rs、typescript/1930-unique-length-3-palindromic-subsequences.ts 等文件均提供了对应语言的位掩码版本,可对照学习各语言位运算写法。
七种解法复杂度总览
| 解法 | 思路 | 时间复杂度 | 空间复杂度 | 是否适用于 |
|---|---|---|---|---|
| 1. 递归暴力 | 枚举全部子序列 | 否 | ||
| 2. 三重循环暴力 | 枚举下标三元组 | 否 | ||
| 3. 顺序匹配 | 枚举 676 个候选回文并匹配 | 勉强 | ||
| 4. 遍历中间字符 | 左侧集合 + 右侧频率 | 是 | ||
| 5. 前缀计数 | 前缀表区间查询 | 是 | ||
| 6. 首尾索引 + 集合 | 首末下标间去重 | 是 | ||
| 7. 首尾索引 + 位掩码 | 位掩码替代集合 | 是(推荐) |
为字符串
s的长度, 为唯一长度为 3 的回文子序列数量上限()。
从表中可以清晰看到一条递进主线:递归/枚举(指数级)→ 候选枚举(线性 × 常数)→ 单次扫描(纯线性)→ 常数空间优化。这正是解决"字符串计数去重"类问题的通用思考路径。
常见陷阱(Common Pitfalls)
1. 把"子序列计数"当成"子序列枚举计数"
题目要求的是唯一回文子序列的个数,而非全部子序列的个数。同一个回文(如 "aba")即使以不同下标组合出现多次,也只能计一次。解法 1、2、4 若不使用 set 去重(或解法 6、7 不去重统计不同中间字符),就会严重高估答案。
2. 混淆子序列与连续子串
子序列不要求字符连续,三个字符中间可以隔着任意数量的其他字符,只需保持相对顺序。把问题误当成"找长度为 3 的连续回文子串"是最常见的错误方向,会漏掉 "aabca" 中 "aba" 这类间隔型答案。
3. 中间字符统计过于低效
对每个两端字符对,都需要统计其首末出现位置之间的不同中间字符个数。若对每对两端字符都线性重扫整段子串,最坏会退化为 的多次重复扫描。前缀计数(解法 5)与位掩码(解法 7)分别用空间换时间和常数级位运算解决了这一瓶颈。
仓库实现与延伸阅读
本题在仓库中收录了 8 种语言的实现,除上文引用的之外,还包括:
- c/1930-unique-length-3-palindromic-subsequences.c
- javascript/1930-unique-length-3-palindromic-subsequences.js
- kotlin/1930-unique-length-3-palindromic-subsequences.kt
题目收录情况可在 README.md 的题目总表中检索 "1930" 查看各语言支持状态。若想巩固相关技能,可继续阅读仓库中的关联题解:
- longest-palindromic-subsequence.md:将回文问题推广到任意长度,核心是区间 DP;
- palindromic-substrings.md:回文计数问题的子串版本;
- largest-3-same-digit-number-in-string.md:同样是长度为 3 的字符串模式题,可对比"子串 vs 子序列"的差异。
总结
Unique Length-3 Palindromic Subsequences 是一个"小问题、大思维"的典型题目:字符集只有 26 个字母这一特性,让答案空间被压缩到 676 以内,从而催生了"枚举候选"与"线性扫描 + 常数空间"两类高效解法。掌握从暴力递归到首尾索引 + 位掩码的七级递进,等于同时复习了回溯枚举、集合去重、前缀和与位运算四大基础工具,这些能力可以直接迁移到子序列计数、区间统计、字符串模式匹配等更广泛的问题中。