940. 不同的子序列 II

---

前言

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

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

例如，“ace” 是 “abcde” 的一个子序列，但 “aec” 不是

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/distinct-subsequences-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

没有重复字符的时候

新的子串为{1}

2到来,新加{2},{1,2}

3到来,数量是之前的2倍
{3},{1,3},{2,3},{1,2,3}

有重复字符的时候

第二个1到来,重复了{1},因此新增数量为1

第三个1来了,重复了2个

因此可以推出,假设之前出现的字母的数量为X=100;
那么当下一次出现相同字母的数量为
all=perAll(上一个位置的all)+newAll(如果不重复字母新增的数量)-X;

用一个数组存储26个字母结尾的字符串数量，
all加上之前的all,如果出现过相同的字母,就减去数组中的相同字母的数

来到b,all=2
空串和{b}
来到第一个c,newAll=2,all=4,记录c:2

来到第2个c,newAll=4,all=8
因为c有记录,因此all要减2,

代码

class Solution {
    
    public int distinctSubseqII(String s) {
    
        if (s == null || s.length() == 0) {
    
			return 0;
		}
        char[] str=s.toCharArray();
        int all=1;
        int mod=1000000007;
        int[] map=new int[26];
        for(int i=0;i<str.length;i++){
    
            int newAll=all;
            int curAll=(all+newAll)%mod;
            all=(curAll-map[str[i]-'a']+mod)%mod;
            map[str[i]-'a']=newAll;
        }
        return all-1;
    }
}