> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/distinct-subsequences-ii.md).

# Distinct Subsequences II

Given a string `S`, count the number of distinct, non-empty subsequences of `S` .

Since the result may be large, **return the answer modulo `10^9 + 7`**.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Note:**

1. `S` contains only lowercase letters.
2. `1 <= S.length <= 2000`

```java
class Solution {
    long mod = 1000000007;

    public int distinctSubseqII(String s) {
        long dp[] = new long[s.length() + 1];
        int[] last = new int[26];
        Arrays.fill(last, -1);
        // Base cases
        dp[0] = 0;
        dp[1] = 1;
        last[s.charAt(0) - 'a'] = 0;
        for (int i = 2; i <= s.length(); i++) {
            dp[i] = (dp[i - 1] * 2 + 1) % mod;
            int lastIndex = last[s.charAt(i - 1) - 'a'];
            if (lastIndex != -1)
                dp[i] = (dp[i] - (dp[lastIndex] + 1) + mod) % mod;
            last[s.charAt(i - 1) - 'a'] = i - 1;
        }
        return (int) (dp[s.length()] % mod);
    }
}
```