LeetCode 940. 不同的子序列 II
题目描述
题意分析
给定只含小写英文字母的字符串，统计能得到多少个内容不同的非空子序列，并对
10^9 + 7取模。子序列可以跳过字符，但保留字符的相对顺序，不能重新排列。“不同”按最终字符串内容判断，不按选择了哪些下标判断。重复字符可能让不同的下标选择得到同一个字符串，这些只能计一次。难点是统计新字符带来的新增结果时，准确扣除已经存在的内容。
解法：动态规划记录最近贡献
核心思路
[!blue]
用
total表示当前已处理前缀的不同子序列数量，暂时包含空串，所以初始值为一。读入字符c后，旧子序列可以直接保留，也可以各自在末尾追加c。追加同一字符不会把两个原本不同的字符串变成相同内容，因此新生成的这一组也有total个，未去重前共计2 * total。两组的交集恰好是旧前缀中已经存在、以
c结尾的子序列。假设c上次出现的位置为j，这些结果都能写成“位置j之前的一个子序列，再追加c”：即使原来的最后一个c选在更早位置，也可以把它改选到j，不影响前面的字符顺序。反过来，这种追加方式确实能生成所有旧的、以c结尾的内容。因此，需要扣除的重复数量就是处理上一个
c之前的子序列总数。用last[c]保存这个数，字符从未出现时为零，就得到转移next = 2 * total - last[c]。计算完
next后，将本轮更新前的total写入last[c]，留给下次遇到c去重，再用next替换total。这里保存的是追加之前的数量，不能写成新总数，也不是保存字符位置或出现次数。所有状态都按模数维护，加减乘法与取模兼容。减法可能得到负余数，需要补上模数。最终
total仍包含空串，返回前再减一并规范到非负余数。
解题步骤
- 初始化
total = 1，创建全部为零的 26 项数组last。- 读取字符下标
idx，计算next = (2 * total - last[idx]) % MOD；若为负则加上MOD。- 将旧
total保存到last[idx]，再令total = next。- 处理完全部字符，返回
(total - 1 + MOD) % MOD，排除空子序列。
代码实现
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(1)$，小写字母表大小固定，只保存 26 项历史贡献和常量个计数变量。
关键点总结
[!green]
- 追加当前字符得到的新集合内部不重复，重复只发生在它与保留的旧集合之间。
- 旧的、以当前字符结尾的全部内容，对应上次追加该字符之前的子序列集合。
- 空串保留在状态中方便统一转移，最终再从答案中扣除。
易错点总结
[!yellow]
- 每轮直接将总数翻倍，会把已经存在的同内容子序列重复计数。
- 把新
total写进last[idx]，会让下次扣掉错误的贡献；应先保存本轮旧总数。- 将
last理解为字符出现次数或最近位置，与转移需要的子序列数量不符。- 忘记对减法产生的负余数做规范化，可能返回负值或污染后续状态。
- 最后不减去一，会把题目不允许的空子序列算入答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1987. 不同的好子序列数目 | 困难 | 原题将字符集限定为二进制并增加前导零规则，可对比按结尾字符计不同子序列的状态。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！