940. Distinct Subsequences II

It is actually a dp solution, but since we only need dp[i-1] to calculate dp, I'm using a prevSum to replace the dp[] array to reduce space usage
prevSum -> dp[i-1] -> result of count of all subsequence of substring [0, i-1]
The tricky part is how can we eliminate duplicates
When a new char s.charAt(i) comes, we can decide either append it to previous strings or not
---> If we do append, we can append current char to all previous sub strings ->  This is the most tricky part!!!!
e.g. c a a
1c-> c
2a-> ca a |  c
3caa-> caa aa ca a | ca a c
See the 3rd line, the "append" part will always cover the previous "append" part, so we are not adding the count of "end with a" by (prevSum + 1) -> we are actually REPLACING the count of "end with a" by (prevSum + 1)
---> If we decide to skip, we only care about all previous results that not end with "a"

98.80 %
class Solution {
    public int distinctSubseqII(String S) {
//  a b c     
//  a -> a
//  b -> ab  b
//  c -> ac abc bc c
//                      1 append          2 skip
//  a b a 
//  a ->  a                a                ""     
//  b ->  ab b             ab  b            a "" 
//  a ->  aa aba ba a      aba ba aa a      ab b a ""  -> exclude all answers end with current char
long[] counter = new long[26];
long prevSum = 0;
long mod = (long)(1e9 + 7);
long curr = 0;
for (int i = 0; i < S.length(); i++) {
// append
curr = prevSum + 1; // append to all previous sub sequences or append itself
int index = S.charAt(i) - 'a';
counter[index] = curr;
for (int j = 0; j < 26; j++) {
if (j != index) {
curr += counter[j];
}
}
curr = curr % mod;
prevSum = curr; // result of substring [0, i]
}
return (int)curr;
}
}