<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:
        MOD = 10**9 + 7
        n = len(s)
        dp = [0] * n
        index_map = {} # 最後の文字のインデックスを入れる場所
        dp[0] = 1
        index_map[s[0]] = 0

        for i in range(1, n):
            num_of_pattern_without_char = dp[i-1] # => current, prev パターンかと思ったが、 i, i-1 パターン
            num_of_pattern_with_char = dp[i-1]
            num_of_empty_string = 1
            num_of_pattern_without_consideration_of_duplication = (num_of_pattern_without_char + num_of_empty_string) + (num_of_pattern_with_char + num_of_empty_string) - num_of_empty_string

            char, duplication = s[i], 0 # => 空文字が一つ残っていないと、その文字一つだけの場合をカウントできない
            if char in index_map:
                last_char_index = index_map[char]
                if last_char_index == 0:
                    duplication = num_of_empty_string
                else:
                    duplication = dp[last_char_index-1]+num_of_empty_string # => dp[last_index] だと char を含まない文字列が入ってしまう => dp[last_index-1]+num_of_empty_string　にすることで、last_index-1 から確実に char が含まれている文字列に限定している

            dp[i] = num_of_pattern_without_consideration_of_duplication - duplication
            index_map[char] = i

        return dp[-1] % MOD
17100