940. Distinct Subsequences II

Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 10^9 + 7.A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not.

Example 1:

Input: s = "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2:

Input: s = "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".

Example 3:

Input: s = "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

Constraints:

• 1 <= s.length <= 2000

• s consists of lowercase English letters.

Solution

The key is to understand the distinct count for the string in the c,

endWith[c-'a'] = endWith[0]+endWith[1]+.....endWith[26 ] + 1;

class Solution {
    public int distinctSubseqII(String s) {
        long mod = (long)1e9 + 7;
        long[] ends = new long[26];
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            long sum = 0;
            for(long end : ends){
                sum += end;
            }
            ends[c-'a'] = (sum % mod) + 1; 
        }
        long sum = 0;
        for(long end : ends){
            sum += end;
        }
           
        return (int)(sum % mod);
    }
}