LeetCode 1930 Unique Length-3 Palindromic Subsequences 七种解法全解:从暴力递归到位掩码优化的完整思维链

原创2026-09-18 20:03:431,608 阅读
文章标签:示例工程教程

LeetCode 1930 Unique Length-3 Palindromic Subsequences 七种解法全解:从暴力递归到位掩码优化的完整思维链

本篇技术指南以 LeetCode 1930「Unique Length-3 Palindromic Subsequences」(唯一长度为 3 的回文子序列)为核心,完整讲解从 O(2n)O(2^n) 暴力递归到 O(26n)O(26n) 位掩码优化的七种解法,并对照本仓库(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=67626 \times 26 = 676 种(26 种首尾字符 × 26 种中间字符)。这个上界 m = 676 反复出现在复杂度分析中。

围绕这三点,可以从"生成候选"与"统计存在性"两个角度派生出七种复杂度迥异的解法,下面的章节逐一展开。


前置知识(Prerequisites)

在动手实现前,需要具备以下基础能力:

  • Hash Set(哈希集合):用于记录唯一回文子序列、避免重复计数,是解法 1、2、4、6 的核心数据结构;
  • String Traversal(字符串遍历):按索引访问字符、维护左右扫描指针;
  • Prefix Sum(前缀和,用于最优解):预计算各字符的出现次数,从而 O(1)O(1) 查询任意区间的字符分布(解法 5);
  • Bit Manipulation(位运算,用于最优解):用 26 位整数掩码表示"某字符是否出现过",实现 O(1)O(1) 空间的去重(解法 7)。

解法一:递归暴力(Recursion)

直觉

既然长度为 3 的回文形如 aba,我们可以用递归生成所有长度为 3 的子序列,再筛选出回文。每一步对当前字符只有两种选择:跳过或纳入,从而穷举全部 2n2^n 种组合。

算法步骤

  1. 用集合 res 存储找到的唯一回文子序列。
  2. 定义递归函数 rec(i, cur),i 为当前扫描到的下标,cur 为正在构造的子序列。
  3. 若 cur 长度达到 3:判断 cur[0] == cur[2],成立则加入 res,随后返回。
  4. 若 i 到达字符串末尾,直接返回。
  5. 产生两个递归分支:跳过 s[i](rec(i+1, cur))或纳入 s[i](rec(i+1, cur + s[i]))。
  6. 从 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)

复杂度

  • 时间复杂度:O(2n)O(2^n)——每个字符都有"选/不选"两个分支;
  • 空间复杂度:O(n+m)O(n + m)——递归栈深度 O(n)O(n),加上去重集合最多 m=676m = 676 个字符串。

其中 nn 为字符串 s 的长度,mm 为唯一长度为 3 的回文子序列数量上限(26×26=67626 \times 26 = 676)。

该解法思路最直白,但面对 nn 可达 10510^5 量级的输入必然超时,仅用于理解问题本质。


解法二:三重循环暴力(Brute Force)

直觉

不生成所有子序列,而是用三层嵌套循环直接枚举三个字符的下标三元组 i<j<ki < j < k,检查 s[i] == s[k] 是否成立。集合保证每个唯一回文只计一次。

算法步骤

  1. 用集合 res 存储唯一回文子序列。
  2. 枚举 i 从 0 到 n-3,j 从 i+1 到 n-2,k 从 j+1 到 n-1。
  3. 若 s[i] == s[k],将字符串 s[i] + s[j] + s[k] 加入 res。
  4. 返回 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)

复杂度

  • 时间复杂度:O(n3)O(n^3);
  • 空间复杂度:O(m)O(m)。

nn 为字符串长度,mm 为唯一长度为 3 的回文子序列数量上限(676)。

三层循环虽然避免了递归开销,但 O(n3)O(n^3) 的代价在数据规模稍大时依然不可接受,适合作为对照基线。


解法三:顺序匹配枚举全部回文(Sequential Matching)

直觉

观察上界:候选回文总共只有 26×26=67626 \times 26 = 676 个。既然如此,不如反过来——枚举所有候选回文 ends + mid + ends,对每个候选在字符串中做一次顺序匹配(类似子序列判定),能匹配上就计数。匹配的复杂度为 O(n)O(n),总代价为 O(n×m)O(n \times m)。

算法步骤

  1. 初始化 res = 0。
  2. 外层枚举首尾字符 ends(a 到 z),内层枚举中间字符 mid(a 到 z)。
  3. 构造序列 seq = ends + mid + ends。
  4. 用一个游标 idx 顺序扫描 s:每当 s 中字符等于 seq[idx] 就推进 idx;当 idx 到达 3 说明匹配成功,res 加 1 并跳出。
  5. 返回 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

复杂度

  • 时间复杂度:O(n×m)O(n \times m),其中 m=676m = 676 为候选回文总数;
  • 空间复杂度:O(1)O(1),仅使用常数级变量。

nn 为字符串长度,mm 为唯一长度为 3 的回文子序列数量上限(26×26=67626 \times 26 = 676)。

这是"枚举候选 + 判定存在"思想的直接体现,常数因子 676 使其在 n=105n = 10^5 时约执行 6.76×1076.76 \times 10^7 次基本操作,属于可接受的折中方案。


解法四:遍历中间字符(Iterate On Middle Characters)

直觉

前几种解法要么枚举三元组、要么枚举候选,都是"以两端为中心"。换个视角:以中间字符为中心。回文 x m x 存在,当且仅当字符 x 同时出现在中间字符 m 的左侧与右侧。于是只需遍历每个位置作为中间字符,维护"左侧已见字符集合"与"右侧剩余字符频率",统计两侧交集即可。

算法步骤

  1. 统计 s 中每个字符的总频率(代表初始的"右侧"字符分布)。
  2. 维护"左侧已见字符"集合 left(初始为空)。
  3. 用集合 res 存储 (中间字符, 两端字符) 二元组以去重。
  4. 遍历每个 s[i]:
    • 先在右侧频率中把 s[i] 减一(若减到 0 则移除,表示右侧不再有该字符);
    • 遍历 26 个字母 c,若 c 同时出现在 left 与右侧频率中,说明 c + s[i] + c 是有效回文,加入 res;
    • 把 s[i] 加入 left。
  5. 返回 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])。

复杂度

  • 时间复杂度:O(26×n)O(26 \times n),每步最多检查 26 个字母;
  • 空间复杂度:O(m)O(m),res 最多容纳 676 个二元组。

nn 为字符串长度,mm 为唯一长度为 3 的回文子序列数量上限(676)。

这一解法将问题从"枚举"降为"单次线性扫描",是理解最优解的关键过渡。


解法五:前缀计数(Prefix Count)

直觉

回文 c ... x ... c 存在,等价于:字符 c 至少出现两次(取首次 l 与末次 r),且在区间 (l, r) 内存在某个字符 x。若我们能 O(1)O(1) 回答"区间 (l, r) 内是否出现字符 x",就能以 O(26)O(26) 完成对每个 c 的统计。前缀计数数组正是为此服务的:prefix[i][c] 表示 s[0..i-1] 中字符 c 的出现次数,任意区间 (l, r) 的计数差 prefix[r][c] - prefix[l+1][c] 即可 O(1)O(1) 求得。

算法步骤

  1. 构建前缀计数数组 prefix[i][c] = s[0..i-1] 中字符 c 的数量。
  2. 同时记录每个字符的首次下标 firstIndex 与末次下标 lastIndex。
  3. 对每个出现至少两次的字符(firstIndex != lastIndex):
    • 令 l = firstIndex,r = lastIndex;
    • 对 26 个候选中间字符 mid,若 prefix[r][mid] - prefix[l+1][mid] > 0,说明区间内存在该字符,答案加 1。
  4. 返回总数。
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

复杂度

  • 时间复杂度:O(26×n)O(26 \times n)——构建前缀表 O(26n)O(26n),统计阶段 26×2626 \times 26 次 O(1)O(1) 查询;
  • 空间复杂度:O(26×n)O(26 \times n)——二维前缀表。

前缀计数是"区间统计"类问题的通用武器,代价是 O(26n)O(26n) 的空间。接下来两种解法会在不牺牲时间的前提下把空间压回 O(1)O(1)。


解法六:首尾索引 + 集合(First And Last Index)

直觉

回文两端字符必须相同且至少出现两次。对每个字符 c,能够作为中间字符的,必然是首次出现与末次出现之间的某个字符。因此只需定位 c 的首末下标 l、r,把 s[l+1 .. r-1] 中的不同字符个数累加即可——这些不同字符每个都能与两端 c 组成一个唯一回文 c x c。

算法步骤

  1. 对字符 c(a 到 z):
    • 用 find / rfind(或 indexOf / lastIndexOf)求出 l、r;
    • 若 c 未出现或只出现一次(l == -1 或 l == r),跳过;
    • 将区间 (l+1, r-1) 内的字符收集进集合 mids;
    • res += len(mids)。
  2. 返回 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 版本,可作为对照。

复杂度

  • 时间复杂度:O(26×n)O(26 \times n)——对 26 个字符各做一次区间扫描;
  • 空间复杂度:O(1)O(1)——集合 mids 最多容纳 26 个不同字符。

由于最多只有 26 个不同字符,mids 规模有常数上界,因此空间可视为 O(1)O(1)。


解法七:首尾索引 + 位掩码(First And Last Index, Optimal)

直觉

解法六的集合去重有常数开销。既然中间字符只有 26 种,完全可以用一个 26 位整数位掩码 表示"哪些字符已在区间内出现过":第 c 位为 1 表示字符 c 已计入。判断 mask & (1 << c) 是否为 0 即可 O(1)O(1) 判重,置位 mask |= (1 << c) 即可标记。这是位运算替代集合的经典技巧。

算法步骤

  1. 第一遍扫描:记录每个字符的 firstIndex 与 lastIndex。
  2. 对每个至少出现两次的字符:
    • 令 l = firstIndex,r = lastIndex;
    • 初始化 mask = 0;
    • 遍历 i 从 l+1 到 r-1:若 mask & (1 << c) 为 0,则置位并让结果加 1。
  3. 返回总数。
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

复杂度

  • 时间复杂度:O(26×n)O(26 \times n)——两遍线性扫描,内层位运算均为 O(1)O(1);
  • 空间复杂度:O(1)O(1)——仅两个长度 26 的索引数组与一个整数掩码。

由于最多只有 26 个不同字符,辅助空间有常数上界,因此空间为 O(1)O(1)。

该解法同时满足"时间线性、空间常数"两个目标,是面试与竞赛场景下的推荐实现。仓库中 cpp/1930-unique-length-3-palindromic-subsequences.cpp、rust/1930-unique-length-3-palindromic-subsequences.rs、typescript/1930-unique-length-3-palindromic-subsequences.ts 等文件均提供了对应语言的位掩码版本,可对照学习各语言位运算写法。


七种解法复杂度总览

解法 思路 时间复杂度 空间复杂度 是否适用于 n=105n = 10^5
1. 递归暴力 枚举全部子序列 O(2n)O(2^n) O(n+m)O(n + m) 否
2. 三重循环暴力 枚举下标三元组 O(n3)O(n^3) O(m)O(m) 否
3. 顺序匹配 枚举 676 个候选回文并匹配 O(n×m)O(n \times m) O(1)O(1) 勉强
4. 遍历中间字符 左侧集合 + 右侧频率 O(26n)O(26n) O(m)O(m) 是
5. 前缀计数 前缀表区间查询 O(26n)O(26n) O(26n)O(26n) 是
6. 首尾索引 + 集合 首末下标间去重 O(26n)O(26n) O(1)O(1) 是
7. 首尾索引 + 位掩码 位掩码替代集合 O(26n)O(26n) O(1)O(1) 是(推荐)

nn 为字符串 s 的长度,mm 为唯一长度为 3 的回文子序列数量上限(26×26=67626 \times 26 = 676)。

从表中可以清晰看到一条递进主线:递归/枚举(指数级)→ 候选枚举(线性 × 常数)→ 单次扫描(纯线性)→ 常数空间优化。这正是解决"字符串计数去重"类问题的通用思考路径。


常见陷阱(Common Pitfalls)

1. 把"子序列计数"当成"子序列枚举计数"

题目要求的是唯一回文子序列的个数,而非全部子序列的个数。同一个回文(如 "aba")即使以不同下标组合出现多次,也只能计一次。解法 1、2、4 若不使用 set 去重(或解法 6、7 不去重统计不同中间字符),就会严重高估答案。

2. 混淆子序列与连续子串

子序列不要求字符连续,三个字符中间可以隔着任意数量的其他字符,只需保持相对顺序。把问题误当成"找长度为 3 的连续回文子串"是最常见的错误方向,会漏掉 "aabca" 中 "aba" 这类间隔型答案。

3. 中间字符统计过于低效

对每个两端字符对,都需要统计其首末出现位置之间的不同中间字符个数。若对每对两端字符都线性重扫整段子串,最坏会退化为 O(26×n)O(26 \times n) 的多次重复扫描。前缀计数(解法 5)与位掩码(解法 7)分别用空间换时间和常数级位运算解决了这一瓶颈。


仓库实现与延伸阅读

本题在仓库中收录了 8 种语言的实现,除上文引用的之外,还包括:

题目收录情况可在 README.md 的题目总表中检索 "1930" 查看各语言支持状态。若想巩固相关技能,可继续阅读仓库中的关联题解:

总结

Unique Length-3 Palindromic Subsequences 是一个"小问题、大思维"的典型题目:字符集只有 26 个字母这一特性,让答案空间被压缩到 676 以内,从而催生了"枚举候选"与"线性扫描 + 常数空间"两类高效解法。掌握从暴力递归到首尾索引 + 位掩码的七级递进,等于同时复习了回溯枚举、集合去重、前缀和与位运算四大基础工具,这些能力可以直接迁移到子序列计数、区间统计、字符串模式匹配等更广泛的问题中。

登录后查看全文
leetcode