940. Different subsequences II

---

前言

给定一个字符串 s,计算 s 的 different non-empty subsequences 的个数.因为结果可能很大,So returning an answer needs to be right 10^9 + 7 取余 .

字符串的 子序列 is to remove some via the original string（也可能不删除）characters without changing the relative positions of the remaining characters.

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

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

解题思路

when there are no repeating characters

The new substring is{1}

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

3到来,Quantity is before2倍
{3},{1,3},{2,3},{1,2,3}

when there are repeated characters

第二个1到来,重复了{1},Therefore, the number of new additions is 1

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

因此可以推出,Suppose the number of letters that appear before is X=100;
Then the number of the next occurrence of the same letter is
all=perAll(上一个位置的all)+newAll(The number of new letters if not repeated)-X;

用一个数组存储26The number of strings ending in letters,
all加上之前的all,If the same letter appears,Just subtract the number of the same letter in the array

来到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;
    }
}