0940：不同的子序列 II（1985 分）

力扣第 110 场周赛第 4 题

题目

给定一个字符串 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 仅由小写英文字母组成

相似问题：

• 1987：不同的好子序列数目（2422 分）
• 2842：统计一个字符串的 k 子序列美丽值最大的数目（2091 分）

分析

#1

• 假如 s 末尾字符为 ‘a’
  • ‘a’ 可以和 s[:-1] 的每个序列组成新的序列
  • ‘a’ 自身 1 个序列
  • s[:-1] 的每个 ‘a’ 结尾的序列都在新的序列集合里，都是重复的
• 因此令 f[i][c] 代表 s[:i+1] 的 c 结尾的序列个数，即可递推
  • f[i][s[i]] = sum(f[i-1])+1

1
2
3
4
5
6
7
8

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9+7
        f = [0]*26
        for i,c in enumerate(s):
            c = ord(c)-ord('a')
            f[c] = (sum(f)+1)%mod
        return sum(f)%mod

16 ms

#2

• 额外维护一个变量 g 代表 sum(f)，可以优化时间

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10**9+7
        f = [0]*26
        g = 0
        for i,c in enumerate(s):
            c = ord(c)-ord('a')
            add = g+1-f[c]
            f[c] = (f[c]+add)%mod
            g = (g+add)%mod
        return g
        

7 ms