# Distinct Subsequences II
**Difficulty:** HARD
[External](https://leetcode.com/problems/distinct-subsequences-ii)
Canonical: https://scaleengineer.com/dsa/problems/distinct-subsequences-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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.

# Approaches
## Dynamic Programming with O(N) Space
This approach uses dynamic programming to build up the count of distinct subsequences. We define `dp[i]` as the number of distinct non-empty subsequences for the prefix of the string of length `i`. We iterate through the string and calculate `dp[i]` based on `dp[i-1]` and the last occurrence of the current character.
**Time:** O(N), where N is the length of the string. We iterate through the string once, and all operations inside the loop are constant time. · **Space:** O(N), where N is the length of the string. This is for the `dp` array. The `last` array uses O(1) space as the alphabet size is constant.
**Pros:** A standard and conceptually clear dynamic programming solution.; Correctly handles all cases, including duplicate characters.
**Cons:** Requires O(N) extra space for the DP table, which is not optimal.
### Explanation
We can solve this problem using dynamic programming. Let `dp[i]` be the number of distinct non-empty subsequences of `s.substring(0, i)`. Our goal is to find `dp[n]`, where `n` is the length of `s`.

The base case is `dp[0] = 0`, as there are no non-empty subsequences in an empty string.

Now, let's find the recurrence relation. When we move from `s[0...i-2]` to `s[0...i-1]`, we introduce a new character `c = s[i-1]`. The distinct subsequences of `s[0...i-1]` consist of:
1. The distinct subsequences of `s[0...i-2]` (which is `dp[i-1]`).
2. New subsequences formed by appending `c` to existing subsequences of `s[0...i-2]` (including the empty subsequence). The number of such subsequences is `dp[i-1] + 1`.

If `c` is a new character that has not appeared in `s[0...i-2]`, then all these `dp[i-1] + 1` new subsequences are unique. So, `dp[i] = dp[i-1] + (dp[i-1] + 1) = 2 * dp[i-1] + 1`.

If `c` has appeared before, say its last occurrence was at index `j-1` (where `j < i`), then we have double-counted. The subsequences we are adding are `{sub + c | sub is a subsequence of s[0...i-2]}`. The duplicates are those that are identical to `{sub' + c | sub' is a subsequence of s[0...j-2]}`. The number of such duplicates is `dp[j-1] + 1`. 

So, we must subtract this count. The recurrence becomes `dp[i] = (2 * dp[i-1] + 1) - (dp[j-1] + 1) = 2 * dp[i-1] - dp[j-1]`. We can use an array `last` to keep track of the last seen index of each character to find `j` efficiently. All calculations must be done modulo `10^9 + 7`, being careful with subtraction.

```java
class Solution {
    public int distinctSubseqII(String s) {
        int MOD = 1_000_000_007;
        int n = s.length();
        long[] dp = new long[n + 1];
        dp[0] = 0;

        // last[char] stores the 1-based index i where the character was last seen.
        int[] last = new int[26];

        for (int i = 1; i <= n; i++) {
            char c = s.charAt(i - 1);
            int charIndex = c - 'a';
            
            // Base recurrence: double the previous count.
            dp[i] = (2 * dp[i - 1]) % MOD;
            
            int prevIdx = last[charIndex];
            if (prevIdx == 0) { // First time seeing this character
                // Add 1 for the single-character subsequence itself.
                dp[i] = (dp[i] + 1) % MOD;
            } else { // Character has been seen before
                // Subtract the count of subsequences that were formed with the previous occurrence of c.
                // This count is dp[prevIdx - 1].
                dp[i] = (dp[i] - dp[prevIdx - 1] + MOD) % MOD;
            }
            
            last[charIndex] = i;
        }

        return (int) dp[n];
    }
}
```
### Algorithm
- Let `dp[i]` be the number of distinct non-empty subsequences of the prefix `s[0...i-1]`.
- The base case is `dp[0] = 0` for an empty string.
- To compute `dp[i]`, we consider the character `c = s[i-1]`. The new subsequences are formed by taking all `dp[i-1]` subsequences of `s[0...i-2]` and appending `c` to them, plus the single character subsequence `c`. This gives `dp[i-1] + 1` new subsequences.
- The total count becomes `dp[i] = dp[i-1] (old ones) + (dp[i-1] + 1) (new ones) = 2 * dp[i-1] + 1`.
- If `c` has appeared before at a 1-based index `j`, we have overcounted. The number of overcounted subsequences is the number of subsequences that could be formed with the previous `c`, which is `dp[j-1] + 1`.
- The corrected recurrence is `dp[i] = (2 * dp[i-1] + 1) - (dp[j-1] + 1) = 2 * dp[i-1] - dp[j-1]`.
- We use an auxiliary array `last` to store the most recent 1-based index of each character.
- The final answer is `dp[n]`, with all calculations performed modulo `10^9 + 7`.

## Optimized Dynamic Programming with O(1) Space
This approach improves upon the previous DP solution by optimizing the space complexity. Instead of tracking the total count of subsequences at each step, we track the number of distinct subsequences ending with each character. This allows us to compute the result with constant extra space.
**Time:** O(N), where N is the length of the string. We perform a single pass with constant time operations inside the loop. · **Space:** O(1), as we only use an array of constant size (26 for the alphabet) and a few variables, regardless of the input string length.
**Pros:** Highly efficient in both time and space.; Optimal O(1) space complexity (relative to alphabet size).
**Cons:** The logic might be slightly less intuitive to derive compared to the O(N) space DP approach.
### Explanation
A more memory-efficient dynamic programming approach can be devised by changing the DP state. Instead of storing the total count of distinct subsequences at each prefix length, we can store the count of distinct subsequences ending with each character of the alphabet.

Let `ends_with[c]` be the number of distinct subsequences of the prefix processed so far that end with character `c`. We iterate through the input string `s`. For each character `c` in `s`:

1. The total number of distinct subsequences for the prefix processed *before* the current character is the sum of all values currently in the `ends_with` array. Let's maintain this sum in a variable `total_distinct`.
2. When we process the current character `c`, we can form new subsequences ending with `c`. These are formed by appending `c` to every existing distinct subsequence, plus the single-character subsequence `c` itself. The number of such new subsequences is `total_distinct + 1`.
3. We update `ends_with[c]` to this new value: `ends_with[c] = (total_distinct + 1) % MOD`. This update correctly handles duplicates. By setting a new value, we are implicitly replacing the old subsequences that ended with `c` with a new, larger set of subsequences ending with `c`. The net effect is that we only count the distinct ones.
4. The `total_distinct` count is then updated by the net change, which is `new_count - old_count`.

The final answer is the `total_distinct` count after iterating through the entire string.

```java
class Solution {
    public int distinctSubseqII(String s) {
        int MOD = 1_000_000_007;
        // endsWith[i] stores the number of distinct subsequences ending with character 'a' + i
        long[] endsWith = new long[26];
        long totalDistinct = 0;

        for (char c : s.toCharArray()) {
            int charIndex = c - 'a';
            
            // The number of new subsequences ending with c is the total number of
            // distinct subsequences seen so far (totalDistinct) plus 1 (for c itself).
            long newEndsWithC = (totalDistinct + 1) % MOD;
            
            // The old count for subsequences ending with c.
            long oldEndsWithC = endsWith[charIndex];
            
            // Update the total count. The net change is (newEndsWithC - oldEndsWithC).
            totalDistinct = (totalDistinct + newEndsWithC - oldEndsWithC + MOD) % MOD;
            
            // Update the count for subsequences ending with c.
            endsWith[charIndex] = newEndsWithC;
        }

        return (int) totalDistinct;
    }
}
```
### Algorithm
- Initialize an array `ends_with` of size 26 to all zeros. `ends_with[i]` will store the count of distinct subsequences ending with character `'a' + i`.
- Initialize `total_distinct = 0`, which will be the running sum of all values in `ends_with`.
- Define `MOD = 10^9 + 7`.
- Iterate through each character `c` of the string `s`:
  a. Let `char_idx = c - 'a'`.
  b. Store the old count of subsequences ending with `c`: `old_count = ends_with[char_idx]`.
  c. The new count of subsequences ending with `c` is the total number of distinct subsequences seen so far, plus one (for the character `c` itself): `new_count = (total_distinct + 1) % MOD`.
  d. Update `ends_with[char_idx] = new_count`.
  e. Update the `total_distinct` count by adding the net change: `total_distinct = (total_distinct + new_count - old_count + MOD) % MOD`.
- After the loop, `total_distinct` holds the final answer.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int distinctSubseqII(String s) {
    int[] dp = new int[26];
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
      int j = s.charAt(i) - 'a';
      int add = (ans - dp[j] + 1) % MOD;
      ans = (ans + add) % MOD;
      dp[j] = (dp[j] + add) % MOD;
    }
    return (ans + MOD) % MOD;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int distinctSubseqII(string s) {
    vector<long> dp(26);
    long ans = 0;
    for (char &c : s) {
      int i = c - 'a';
      long add = ans - dp[i] + 1;
      ans = (ans + add + mod) % mod;
      dp[i] = (dp[i] + add) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def distinctSubseqII(self, s: str) -> int: mod = 10 ** 9 + 7 dp = [0] * 26 ans = 0 for c in s: i = ord(c) - ord('a') add = ans - dp[i] + 1 ans = (ans + add) % mod dp[i] += add return ans

```