<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:
    //backtracking solution
    int solve(int idx, string &s, string &curr, set<string> &st){

        if(idx == s.size()){

            if(st.find(curr) == st.end()){
                st.insert(curr);
                return 1;
            }
            else{
                return 0;
            }
        }


        curr.push_back(s[idx]);
        int take = solve(idx+1,s,  curr, st);
        curr.pop_back();
        int not_take = solve(idx+1, s, curr, st);

        return take + not_take;
    }
    
    int mod = 1e9+7;
    int distinctSubseqII(string s) {
        
        int n = s.size();
        int dp[n];
        dp[0] = 1;

        unordered_map<int, int> mp;
        mp[s[0] - 'a'] = 0;

        for(int i = 1; i<n; i++){

            //unique
            if(mp.find(s[i] - 'a') == mp.end()){
                long long temp= ((2*dp[i-1])%mod + 1)%mod;
                dp[i] = temp%mod;
                mp[s[i] - 'a'] = i;
            }
            else{
                int idx = mp[s[i] - 'a'];
                if(idx == 0){
                    long long temp = (2*dp[i-1])%mod;
                    dp[i] = temp%mod;
                }
                else{
                    long long temp = (2LL * dp[i-1] + mod - dp[idx-1]) % mod;
                    dp[i] = temp;
                }
                mp.erase(s[i] - 'a');
                mp[s[i] - 'a'] = i;
            } 
            
        }

        for(auto it: dp){
            cout<<it<<" ";
        }

        return dp[n-1]%mod;;
    }
};
11800