<p>Given a string s, return <em>the number of <strong>distinct non-empty subsequences</strong> of</em> <code>s</code>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>
A <strong>subsequence</strong> 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., <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;<u>a</u>b<u>c</u>d<u>e</u>&quot;</code> while <code>&quot;aec&quot;</code> is not.
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abc&quot;
<strong>Output:</strong> 7
<strong>Explanation:</strong> The 7 distinct subsequences are &quot;a&quot;, &quot;b&quot;, &quot;c&quot;, &quot;ab&quot;, &quot;ac&quot;, &quot;bc&quot;, and &quot;abc&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aba&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> The 6 distinct subsequences are &quot;a&quot;, &quot;b&quot;, &quot;ab&quot;, &quot;aa&quot;, &quot;ba&quot;, and &quot;aba&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaa&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The 3 distinct subsequences are &quot;a&quot;, &quot;aa&quot; and &quot;aaa&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 2000</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        # how long can s be? 2000 letters
        # of lowercase letters

        # the number of distinct nonempty subsequences of s
        # dp[0] = 1

        # if we do it by letter + length, then we have a 
        # brute force, to hash all the subsequences and count them

        # adding a letter to a collection of distinct subsequences will make them all distinct
        # so if this is the first time seeing this letter, we can add it to any of the distinct subsequences
        # if we're already seen it, we can again do dp[i-1] * 2 to add it to all the previuos ones, but we also need to remove some. Specifically, the ones before the previous encounter of this letter, those are the ones that get double counted
        dp = [0] * len(s)
        prev_occ = {s[0] : 0}
        dp[0] = 1
        for i in range(1, len(s)):
            if s[i] not in prev_occ:
                dp[i] = dp[i-1] * 2 + 1 # we can attach any letter
            else:
                prev = prev_occ[s[i]]
                if prev > 0:
                    dp[i] = dp[i-1] * 2 - dp[prev-1]
                else:
                    dp[i] = dp[i-1] * 2
            prev_occ[s[i]] = i
        return dp[-1] % (10 ** 9 + 7)
            
16900