子序列数目

输入：s = "abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

难度：hard

class Solution {
    //状态转移方程真的不好写，所以我不想用动态规划
    //思路：以c结尾的子串数目等于：以c之前的所有字母结尾的子序列数目的总和+1
    public int distinctSubseqII(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int[] alphaBet  = new int[26];
        for(int i=0;i<n;i++){
            long sum = 0;
            //求总和
            for(int j:alphaBet)sum=(sum+j)%1000000007;
            //+1即加上自身
            alphaBet[arr[i]-'a'] = (int)sum+1;
        }
        long res = 0;
        for(int i : alphaBet) res = (res+i)%1000000007;
        return (int)res;
    }
}