<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 {
public:
    const int mod = 1e9+7;
    int distinctSubseqII(string s) {
        int n=s.size();
        map<char,vector<int>> mp;
        for(int i=0;i<n;i++){
            mp[s[i]].push_back(i);
        }
        vector<int> dp(n,0);
        dp[0]=1;
        //dp[i] = no of distinct subsequences in s[0...j]
        for(int i=1;i<n;i++){
            
            //If i is the first occurence of s[i]
            if(mp[s[i]][0] == i){
                //no of subsequences till i-1 => take or not take s[i] with them, 
                //plus s[i] itself
                //dp[i] = dp[i-1]*2 + 1
                dp[i] = (((dp[i-1]%mod)*2)%mod + 1)%mod;
            }
            //Else, if j is the occurence of s[i] before i
            //Get all substring from dp[i-1]
            //Minus, repeating subsequences, all subsequences till s[j-1], taken with s[j]
            //Now also taken with s[i]
            else{
                int idx = lower_bound(mp[s[i]].begin(), mp[s[i]].end(), i)-mp[s[i]].begin();
                int j = mp[s[i]][idx - 1];
                //Here, +1 is not being done for s[i] as subsequence itself since
                //it is already counted as part of dp[j] or before
                //If j==0, j-1 has no subsequences, therefore no repetitions
                if(j==0){
                    //dp[i] = dp[i-1]*2
                    dp[i] = ((dp[i-1]%mod)*2)%mod;
                }
                else{
                    //dp[i] = dp[i-1]*2 - dp[j-1]
                    dp[i] = (((dp[i-1]%mod)*2)%mod - (dp[j-1]%mod))%mod;
                    if(dp[i]<0) dp[i]+=mod;
                }

            }
        }
        return dp[n-1];
    }
};
11300