940. 不同的子序列 II

Problem: 940. 不同的子序列 II

思路

这是一道动态规划的题目。我们需要找出字符串中所有的不同子序列的数量。子序列是从原始序列中删除一些（或不删除）元素但不改变剩余元素的顺序形成的新序列。例如，“ace” 是 “abcde” 的一个子序列，但 “aec” 不是。

我们可以使用一个数组 cnt 来记录每个字符最后一次出现的位置。然后，我们遍历字符串，对于每个字符，我们都有两种选择：将其添加到当前的子序列中，或者不添加。如果我们选择添加，那么新的子序列的数量就是当前的子序列的数量的两倍（因为我们可以选择添加或者不添加这个字符到每一个已经存在的子序列中）。但是，这样会导致重复计算那些包含当前字符的子序列，所以我们需要减去这部分的数量，这部分的数量就是在当前字符上一次出现的位置时的子序列的数量。

解题方法

我们首先初始化一个数组 cnt 来记录每个字符最后一次出现的位置，以及一个变量 all 来记录当前的子序列的数量。然后，我们遍历字符串，对于每个字符，我们计算新添加的子序列的数量 newAdd，这个数量等于当前的子序列的数量减去这个字符上一次出现的位置的子序列的数量。然后，我们更新这个字符在 cnt 中的数量，以及 all 的值。最后，我们返回 all - 1，因为我们需要排除空的子序列。

复杂度

时间复杂度:

$O(n)$，其中 $n$ 是字符串的长度。我们需要遍历一次字符串。

空间复杂度:

$O(1)$，我们只需要常数的空间来存储 cnt 和 all。

Code

class Solution {
    public int distinctSubseqII(String s) {
        int mod = 1000000007;
        char[] str = s.toCharArray();
        int[] cnt = new int[26];
        int all = 1, newAdd;
        for(char c : str) {
            newAdd = (all - cnt[c - 'a'] + mod) % mod;
            cnt[c - 'a'] = (cnt[c - 'a'] + newAdd) % mod;
            all = (all + newAdd) % mod;
        }
        return (all - 1 + mod) % mod;

    }
}