326不同子序列计数问题

题解

问题描述

小 U 有一个字符串 s，他想计算该字符串的所有不同非空子序列的个数。子序列是通过删除原字符串中的部分字符（也可以不删除），且保持剩余字符的相对顺序形成的新字符串。

你的任务是帮助小 U 计算 s 的不同非空子序列的总数，并返回对 $10^9 + 7$ 取余的结果。

例如：

• 当 s = "abc" 时，所有不同的非空子序列包括 "a", "b", "c", "ab", "ac", "bc", 和 "abc"，总数为 7。

解题思路

1. 动态规划状态定义:

   • 定义 f[i] 为字符串 s 的前 i 个字符所能形成的不同非空子序列的数量。字典 last 记录每个字符上一次出现的位置。

2. 动态规划转移:

   • 遍历字符串 s，对于每一个字符 c 在索引 i 位置：
     • 如果 c 是第一次出现，即 c 不在 last 中：
       • 则 f[i] = f[i-1] * 2 + 1。这里 f[i-1] * 2 表示在所有前 i-1 个子序列基础上，每个子序列可以选择添加或不添加 c，+1 表示包含只有 c 这个字符的子序列。
     • 如果 c 之前出现过：
       • 则 f[i] = f[i-1] * 2 - f[last[c] - 1]。f[i-1] * 2 同理，但需要减去 f[last[c] - 1]，以消除由上一次出现 c 到当前 c 之间重复形成的子序列，保证每个子序列唯一。
   • 更新 last[c] = i，记录字符 c 的最新出现位置。

代码

mod = int(1e9 + 7)
def solution(s: str) -> int:
    last = {}
    n = len(s)
    f = [0] * (n + 1)
    for i, c in enumerate(s, 1):
        if c not in last:
            f[i] = f[i - 1] * 2 + 1
        else:
            f[i] = f[i - 1] * 2 - f[last[c] - 1]
        last[c] = i
        f[i] %= mod

    return f[-1]

if __name__ == '__main__':
    print(solution("abc") == 7)
    print(solution("aaa") == 3)
    print(solution("abcd") == 15)
    print(solution("abac") == 13)

时间复杂度

• 该算法的时间复杂度为 O(n)，其中 n 是字符串的长度。
• 空间复杂度为 O(n)，用于存储动态规划数组 f 和字符最后出现位置的哈希表 last。