## Algorithm

Problem Name: 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 `109 + 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.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const distinctSubseqII = function(s) {
const n = s.length,
dp = Array(26).fill(0),
a = 'a'.charCodeAt(0),
mod = 1e9 + 7
let res = 0
for(let ch of s) {
const idx = ch.charCodeAt(0) - a
let tmp = 0
for(let i = 0; i  <  26; i++) tmp = (tmp + dp[i]) % mod
tmp = (tmp + 1) % mod
dp[idx] = tmp
}
return dp.reduce((ac, e) => (ac + e) % mod, 0)
};
``````
Copy The Code &

Input

cmd
s = "abc"

Output

cmd
7

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def distinctSubseqII(self, S):
res, end = 0, collections.Counter()
for c in S:
res, end[c] = res * 2 + 1 - end[c], res + 1
return res % (10**9 + 7)
``````
Copy The Code &

Input

cmd
s = "abc"

Output

cmd
7