---

0940. 不同的子序列 II

• 标签：字符串、动态规划
• 难度：困难

题目链接

• 0940. 不同的子序列 II - 力扣

题目大意

描述：

给定一个字符串 $s$。

要求：

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

说明：

• 字符串的「子序列」是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
  • 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。
• $1 \le s.length \le 2000$。
• $s$ 仅由小写英文字母组成。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：动态规划

思路

这道题要求计算字符串 $s$ 的不同非空子序列的个数。

我们可以使用动态规划：

• 定义 $dp[i]$ 表示字符串前 $i$ 个字符的不同子序列个数。
• 对于第 $i$ 个字符 $s[i]$：
  • 如果不选择 $s[i]$，子序列个数为 $dp[i - 1]$。
  • 如果选择 $s[i]$，可以将 $s[i]$ 添加到前面所有子序列的末尾，得到 $dp[i - 1]$ 个新子序列，再加上单独的 $s[i]$，共 $dp[i - 1] + 1$ 个。
  • 但如果 $s[i]$ 之前出现过（在位置 $j$），那么以 $s[i]$ 结尾的子序列中，有 $dp[j - 1]$ 个是重复的，需要减去。

状态转移方程：

• $dp[i] = dp[i - 1] \times 2 + 1$（不考虑重复）
• 如果 $s[i]$ 在位置 $j$ 出现过，$dp[i] = dp[i - 1] \times 2 + 1 - dp[j - 1] - 1 = dp[i - 1] \times 2 - dp[j - 1]$

代码

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)
        
        # last[c] 记录字符 c 最后一次出现时的 dp 值
        last = {}
        dp = 0  # 当前的不同子序列个数（不包括空序列）
        
        for ch in s:
            # 新增的子序列个数
            new_dp = (dp * 2 + 1) % MOD
            
            # 如果字符之前出现过，减去重复的部分
            if ch in last:
                new_dp = (new_dp - last[ch]) % MOD
            
            # 记录当前字符的 dp 值
            last[ch] = dp + 1
            dp = new_dp
        
        return dp

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度。只需要遍历一次字符串。
• 空间复杂度：$O(|\Sigma|)$，其中 $|\Sigma|$ 是字符集大小（这里是 $26$）。需要哈希表记录每个字符的最后出现位置。