> ## Content Index
> Fetch the complete content index at: https://andybase.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 940 Distinct Subsequences II
- URL: https://andybase.com/940-distinct-subsequences-ii/
- Published: 2018-11-12T16:14:18.000Z
- Updated: 2018-11-12T16:14:18.000Z
- Author: andy
- Tags: leetcode, contest, #Migrated-1784083136856, #wp, #wp-post, #Import 2026-07-15 02:38

link [Distinct Subsequences II](https://leetcode.com/problems/distinct-subsequences-ii/?ref=andybase.com)

## Thought

The very first thought here is use DFS to find all distinct subsequences. However it will time out. So my next idea is using dynamic programming to solve it. I'll define a DP array, where DP\[i + 1\] stands for how many distinct subsequences if I use 0,1,...i characters to build sub sequences, **end with character i**. DP\[0\] is special because it stands for empty condition and should always be 1.

Then, the state transfer funtion is:

DP\[i\] = sum(DP\[i-1\], DP\[i-2\], ... DP\[0\])

Next, lets think about dumplicate. Assume the case "abaca". When I see the last 'a', what should I put in DP\[5\]? I should only count DP\[3\],DP\[4\] cause DP\[2\] + 'a' is already computed in DP\[3\]. So I put another dictionary, with character as key, its **last** index so far as value. Then the state transfer function change a little bit to:

DP\[i\] = sum(DP\[i-1\], DP\[i-2\], ... DP\[last\_time\_same\_character\_appears\])

And remember DP\[0\] stands for empty result, when we count final results, we should emit it.

## Code

```
class Solution:
    def distinctSubseqII(self, S):
        """
        :type S: str
        :rtype: int
        """
        MOD = 10**9 + 7
        N = len(S)
        DP = [0] * (N + 1)
        DP[0] = 1
        lookup = collections.defaultdict(int)
        for index, val in enumerate(S):
            q = index
            prev = lookup[val]
            DP[index + 1] = sum(DP[prev:])  % MOD
            lookup[val] = index + 1
        return sum(DP[1:]) % MOD

```

## Runtime

Time: O(n^2)  
Space: O(n)