LeetCode 940. 不同的子序列 II

2026-04-02 HGNULB 约 9 分钟

文章信息 8 个分类 2 个标签

分类

题目描述

✅ 940. 不同的子序列 II

题意分析

题目要数出一个字符串有多少个互不相同的非空子序列。子序列是按原顺序挑出若干位置得到的串，允许不连续；「互不相同」是按最终得到的字符串本身比较，两次不同的下标选法只要拼出同一个串，就只算一个。

这个去重要求是全题的重心。"aba" 里下标 0 和下标 2 各自单独挑出来都是 "a"，必须合并成一个；而 "ab" 和 "ba" 虽然字符集合相同，因为顺序不同，是两个。

约束里有两条关键信号：字符串长度可达 2000，全部由小写字母构成；答案要求对 $10^9 + 7$ 取模。长度 2000 意味着子序列总数量级是 $2^{2000}$，穷举再去重绝无可能；「只有 26 种字符」则暗示可以为每个字母各留一个常数大小的记录位；而要求取模说明我们只需要数量，不需要真的把子序列列出来。

边界上要留意：空串不算在答案里，但推导过程中把它算进去反而更顺，最后减掉即可；整串字符全相同（如 "aaa"）时答案是长度本身，这是检验去重逻辑最灵敏的用例。

解法：动态规划记录最近贡献

核心思路

暴力做法是枚举所有 $2^n$ 个下标子集，各自拼成字符串扔进哈希集合去重，最后看集合大小。$n$ 只要过 30 这条路就断了，更不用说 2000。

瓶颈在于「去重」被推迟成了事后动作：先无差别造出海量重复品，再靠集合把它们压掉。要提速就得反过来——在计数的过程中就把重复扣掉，永远不显式持有任何一个子序列。

换成增量视角：从左往右扫描，考察「前缀每多一个字符，不同子序列的数量怎么变」。把空串也算进去，记扫完前 $i$ 个字符后不同子序列的集合为 $S_i$，数量为 $T_i$。现在读入第 $i$ 个字符 $c$，新的集合 $S_{i+1}$ 由两部分构成：不使用这个 $c$ 的，就是原来的 $S_i$；使用这个 $c$ 且以它结尾的，是把 $S_i$ 中每个串后面接上 $c$，记作 $S_i + c$。两部分之间不可能重复（一部分不以这个位置的 $c$ 结尾、另一部分必然以 $c$ 结尾，这里比较的是字符串本身，只要末字符不同就不同），所以 $T_{i+1} = T_i + S_i + c $。

麻烦出在 $ S_i + c $ 上。追加操作本身不制造重复（不同的串接同一个字符仍然不同），所以 $ S_i + c = T_i$，看似 $T_{i+1} = 2T_i$。但 $S_i + c$ 里的串未必都是新的：如果字符 $c$ 在更早的位置 $j$ 出现过，那一次已经把 $S_j + c$ 整体贡献进了集合，而 $S_j \subseteq S_i$（前缀越长子序列集合只增不减），所以 $S_j + c$ 完全落在 $S_i + c$ 内部，是彻头彻尾的老面孔。除此之外没有别的重复来源。

于是得到转移方程：$T_{i+1} = 2 T_i - T_{j}$，其中 $j$ 是字符 $c$ 上一次出现的位置，$T_j$ 是处理那一次出现之前的总数；若 $c$ 从未出现过则减 0。

落到实现上就是两个状态：一个标量 total 表示当前的 $T_i$（含空串），一个长度 26 的数组 last，last[c] 保存「上一次遇到字符 c 时、处理它之前的 total」。每步先用旧 total 算出 next，再把 last[c] 覆盖成旧 total，最后让 total 前进到 next——三行的先后顺序不能乱，last[c] 存的必须是这一步开始前的值。

初值 total = 1 对应集合 $S_0 = {\varepsilon}$，只有空串；last 全 0 表示每个字母都还没出现过。扫完全串后 total 含空串，减 1 即为答案。

解题步骤

令 total = 1，last 是长度 26 的全零数组。为什么从 1 起步：把空串纳入统计，转移式 $T_{i+1} = 2T_i - T_j$ 才在首字符处也成立；若从 0 起步，第一个字符会算出 0 个子序列。

从左到右遍历字符串，取出当前字符对应的下标 idx。

先计算 next = total * 2 - last[idx]。为什么乘 2：不用当前字符的方案数是 total，用当前字符结尾的方案数也是 total，两部分互不相交。为什么减 last[idx]：这个字符上一次出现时已经把「当时的全部子序列各接一个该字符」贡献过了，那批串这次会被原样重造，必须扣掉。

对 next 取模，若结果为负则加上模数修正。为什么会为负：total * 2 取模之后可能反而小于 last[idx]，减法就跌破零，而计数结果必须是非负余数。

把 last[idx] 更新为这一步开始前的 total，再把 total 更新为 next。为什么是这个顺序：last[idx] 的语义是「处理本次出现之前的总数」，一旦先让 total 前进，存进去的就是处理之后的值，下次减多了。

遍历结束后返回 total - 1。为什么减 1：total 里始终含着空串，而题目只要非空子序列；实现上要写成 (total - 1 + MOD) % MOD，因为 total 取模后可能恰好是 0。

以 s = "aba" 走一遍：初始 total = 1（集合是 ${\varepsilon}$），last 全 0。

第一步读到 'a'：next = 1 * 2 - last['a'] = 2 - 0 = 2。随后 last['a'] 记为旧的 total 也就是 1，total 变成 2。此刻集合是 ${\varepsilon, \texttt{"a"}}$，确实是 2 个。

第二步读到 'b'：next = 2 * 2 - last['b'] = 4 - 0 = 4。last['b'] 记为 2，total 变成 4。集合是 ${\varepsilon, \texttt{"a"}, \texttt{"b"}, \texttt{"ab"}}$，正好 4 个。

第三步读到 'a'：next = 4 * 2 - last['a'] = 8 - 1 = 7。这里减掉的 1 正是第一步那个 'a' 已经贡献过的 $S_0 + \texttt{a} = {\texttt{"a"}}$——把当前 4 个串各接一个 'a' 会得到 "a"、"aa"、"ba"、"aba"，其中 "a" 早已在集合里，是唯一的重复品，扣 1 无误。last['a'] 更新为 4，total 变成 7。此刻集合是 ${\varepsilon, \texttt{"a"}, \texttt{"b"}, \texttt{"ab"}, \texttt{"aa"}, \texttt{"ba"}, \texttt{"aba"}}$，共 7 个。

遍历结束，返回 $7 - 1 = 6$，即 "a"、"b"、"ab"、"aa"、"ba"、"aba" 这六个非空子序列，与预期一致。

再拿全同字符串 s = "aaa" 复核去重逻辑：total 依次是 1、2、3、4（每步都是 $2T - T_{\text{prev}}$，即 $2 \cdot 1 - 0 = 2$、$2 \cdot 2 - 1 = 3$、$2 \cdot 3 - 2 = 4$），最终返回 3，对应 "a"、"aa"、"aaa"，没有任何一个重复被计入。

代码实现

class Solution {
    // 相同字符会制造重复子序列：当前字符接在某些旧子序列后，可能与上一次同字符接出来的结果完全相同。
    private static final int MOD = 1_000_000_007;

    public int distinctSubseqII(String s) {
        long total = 1;
        long[] last = new long[26];

        for (int i = 0; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a';
            long next = (total * 2 - last[idx]) % MOD;
            if (next < 0) {
                next += MOD;
            }

            last[idx] = total;
            total = next;
        }

        return (int) ((total - 1 + MOD) % MOD);
    }
}

func distinctSubseqII(s string) int {
    // 相同字符会制造重复子序列：当前字符接在某些旧子序列后，可能与上一次同字符接出来的结果完全相同。
    const mod int64 = 1000000007

    total := int64(1)
    last := make([]int64, 26)

    for i := 0; i < len(s); i++ {
        idx := int(s[i] - 'a')
        next := (total*2 - last[idx]) % mod
        if next < 0 {
            next += mod
        }

        last[idx] = total
        total = next
    }

    return int((total - 1 + mod) % mod)
}

复杂度分析

时间复杂度：$O(n)$，字符串只被从左到右扫描一遍，每个字符处只做一次乘二、一次减法、一次取模和两次赋值，全是常数操作，与字符集大小和已有子序列数量都无关。

空间复杂度：$O( \Sigma )$，即 $O(26)$ 的常数级，只需一个标量 total 和一个按字母索引的 last 数组；无论字符串多长，占用都不增长。

关键点总结

计数题遇到「互不相同」时，第一反应不该是造出来再去重，而是找出重复的唯一来源并在转移里直接扣掉。这里的来源刻画得极干净：重复品恰好是上一次同字符贡献过的那一整批。

「容斥式减法」能成立，靠的是 $S_j \subseteq S_i$ 这个包含关系——老的贡献集合完整地落在新的贡献集合内部，不多不少，才可以整块相减而不必再做交集分析。

把空串纳入状态是一个典型的技巧：它让转移在首字符处无需特判，代价只是最后减 1。凡是转移式在边界处别扭的计数 DP，都值得试试「加一个虚拟的空状态」。

涉及取模的减法必须立刻补正为非负余数，且最终再减 1 时要再补一次，不能想当然地认为「计数结果一定是正的」。

面试视角：这题的核心不是代码长度而是转移式的推导过程。把「不选 / 选且以它结尾」的二分、以及「重复恰为上次贡献」这两句话讲清楚，比直接写出 2 * total - last[c] 有价值得多，后者面试官会当成背题。

面试视角：常见追问是「如果要求返回以每个字符结尾的不同子序列数怎么办」。可以答成另一种等价状态定义——用 f[c] 直接记录以字符 c 结尾的不同子序列数，转移是 f[c] = 1 + Σf[*]，答案取全部 f 之和；两种写法互为对偶，能同时说出来会加分。

易错点总结

错误写法：转移只写成 next = total * 2，忘记减去重复来源。用例 s = "aba" → 第三步得到 8，最终返回 7，正确答案是 6，多算的正是重复的 "a"。

错误写法：先执行 total = next，再执行 last[idx] = total。用例 s = "aba" → last['a'] 存成了 2 而非 1，第三步算出 $8 - 2 = 6$，最终返回 5，正确答案是 6。

错误写法：last[idx] 记录成上一次该字符处理之后的总数。用例 s = "aaa" → 每步多扣一份，total 依次为 1、2、2、2，最终返回 1，正确答案是 3。

错误写法：total 从 0 起步，不把空串计入。用例 s = "abc" → 每步都是 $2 \times 0 - 0 = 0$，全程停在 0，返回 -1 或 0，正确答案是 7。

错误写法：last 数组初始化为 1，以为要预留空串。用例 s = "ab" → 第一步 $2 - 1 = 1$、第二步 $2 - 1 = 1$，减掉空串后返回 0，正确答案是 3。

错误写法：最后忘记减去空串，直接返回 total。用例 s = "abc" → 返回 8，正确答案是 7。

错误写法：减法取模后不修正负数，直接返回 next。用例任意让 total * 2 % MOD 小于 last[idx] 的长串 → 中间态变成负数并一路传播，最终返回负值。

错误写法：最后写成 (total - 1) % MOD 而不补模数。用例 total 取模后恰为 0 的输入 → 返回 -1，而计数结果不可能为负。

错误写法：用 32 位整型保存 total 并直接计算 total * 2。用例任意使 total 接近 $10^9$ 的长串 → 乘 2 后越过 int 上界变成负数，后续全盘错乱。

错误写法：改用哈希集合存下所有子序列去重。用例长度 2000 的字符串 → 子序列数量是 $2^{2000}$ 量级，内存和时间双双爆掉。

相似题目

题目	难度	考察点
115. 不同的子序列	困难	数的是匹配固定目标串的方案数，按下标区分而不去重
1143. 最长公共子序列	中等	双串二维 DP 求长度最优值，而非单串计数
300. 最长递增子序列	中等	子序列还需满足单调约束，转移依赖数值比较
392. 判断子序列	简单	只判存在性，双指针贪心匹配即可，无需任何计数