每日算法 不同的子序列 II

例题：[940. 不同的子序列 II

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

• 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

// distinctSubseqII 计算 s 的不同非空子序列个数，答案对 10^9+7 取余。
// 思路：按结尾字符分桶。endWith[c] = 以字符 c 结尾的不同子序列个数，
// 每读到一个字符 c 就把 endWith[c] 覆写为 (total + 1)，"覆写"即去重。
func distinctSubseqII(s string) int {
    const MOD = 1_000_000_007
    endWith := [26]int{} // endWith[c]：以字符 c 结尾的不同子序列个数
    for i := 0; i < len(s); i++ {
        c := s[i] - 'a'
        sum := 0 // 当前所有非空子序列总数
        for j := 0; j < 26; j++ {
            // 计算当前字母与非空串的次数（即之前字母的计算总和）
            sum = (sum + endWith[j]) % MOD
        }
        // 覆写，{ X + c | X 为当前所有子序列（含空串）}
        // sum 对应非空 X，+1 对应 X = 空串，即当前字母自身
        endWith[c] = (sum + 1) % MOD
    }
    ans := 0
    for j := 0; j < 26; j++ {
        ans = (ans + endWith[j]) % MOD
    }
    return ans
}

思路：这题主要还是思维大于能力，我们拿一个例子来进行梳理。

重复是怎么产生的

先看不带字母限制的普通情况（比如 "abc"）：每个位置选或不选，非空子序列恰好 2³ − 1 = 7 个，全不同。

但 "aba" 就出问题了，同样是 2³ − 1 = 7 种位置选法，其中 “只选下标 0” 和 “只选下标 2” 都产生字符串 "a"：

选 {0} → "a"
选 {2} → "a"   ← 同一个字符串，数了两次

所以不能按 “位置选法” 计数，得按 “最终字符串” 计数，即用 map 按结尾字符分桶的思维，去记录字符的结果计数 。

按结尾字符分桶

定义 endWith[c] = 以字符 c 结尾的不同子序列个数。（这里的 c 代指任意字符）

妙处在于：一个字符串 = X + c（结尾前的部分 + 结尾字符）。结尾字符固定为 c 时，X 不同 ⇒ 字符串必不同。“结尾字符” 这个维度天然完成了去重，不用再操心 X 内部有没有重复。

遇到 c 时，为什么是 “覆写” 而不是 “累加”

再次读到字符 c 时（设此刻非空子序列总数为 total = Σ endWith）：

• 现在所有以 c 结尾的可行字符串 = { X + c | X 是前面任意一个不同子序列（含空串）}
• 每个 X 唯一映射到一个 X + c，互不相同，且这个集合 ≥ 旧集合（旧的也是 X + c 形式，X 出自更早的前缀，当然还是当前前缀的子序列）

所以直接整体覆写：

endWith[c] = total + 1      // +1 对应 X = 空串，即 "c" 自己

这个 “覆写而不是累加” 就是去重的好操作，旧值被新值完全覆盖，重复的串永远不会被加第二次。

示例 "aba" 走一遍验证

最终 4 + 2 = 6 ，正好应征了示例 2 的结果。