940. Distinct Subsequences II

refer to this:

https://leetcode.com/problems/distinct-subsequences-ii/discuss/192017/JavaC%2B%2BPython-DP-4-lines-O(N)-Time-O(1)-Space

T: O(n)
S: O(1)

class Solution {
    public int distinctSubseqII(String s) {
        long[] end = new long[26];
        long mod = (long)1e9+7;
        
        for (char c : s.toCharArray()) {
            end[c - 'a'] = Arrays.stream(end).sum()%mod + 1;
        }
        return (int)(Arrays.stream(end).sum()%mod);
    }
}
/*
distinct non-empty subsequences

aba ⇒  

dp [0] = s[0] 結尾的 a ⇒ a, “” ⇒ a (空串不計算 = 1

dp [1] = dp[0] + 1 : s[1] 結尾的 b ⇒ base on a, “”, add b ⇒ ab, b  = 2

dp[2] = a, aa, ba, aba = dp [0] + dp [1] +1  = 4  ⇒ []，a，b，ab (s[0]+s[1]+ 空串)  ⇒ 最後面 append a  

⇒ sum(dp)+1

T: O(n)
S: O(1)
*/