Title source

• leetcode：940. Subsequences with different literals

Title Description

class Solution {
    
public:
    int distinctSubseqII(string s) {
    

    }
};

title

Statistics must be in a~z The number of subsequences at the end

class Solution {
    
public:
    int distinctSubseqII(string s) {
    
        std::vector<long> dp(26, 0);
        int mod = 1e9 + 7;
        for(auto &ch : s){
    
            dp[ch - 'a'] = accumulate(dp.begin(), dp.end(), 1l) % mod;
        }

        return accumulate(dp.begin(),dp.end(),0L)%mod;// Sum up 
    }
};

Dynamic programming + Hashtable

Try the model from left to right

If there are no repeated words in the sequence

every , Either choose , Or don't choose . So the length is N The number of subsequences of the sequence of , Namely $2^N$

If we use dynamic programming to solve it , Make $dp[i]$ by $s[\mathrm{1...}i]$ The number of subsequences of （ Contains an empty string ） that ：

• The equation of state transfer is $dp[i+1]=2\ast dp[i]$
• among $dp[0]=1$, For empty strings , Of course, there is only one subsequence , It's an empty string .

What if there are repeated substrings in the sequence ？

• such as “abcbc” in “ab” It can be s[0] + s[1] It can also be s[0] + s[3].
• We use the idea of dynamic programming , This is the time s[i+1] Take it or not , All subsequences produced consist of two parts .
  • Part of it is s[i+1] No , So this molecular sequence and s[i] The corresponding subsequence is the same .
  • Another part s[i+1] take , Then there will be part of this molecular sequence and s[i] Subsequence coincidence of , We need to find out this part and deduct it .
    • If s[i+1] Never appeared before , Then obviously there will be no overlapping parts .
    • If s[i+1] There have been , The location assumption of the last occurrence is last, that dp[last] In fact, it is the overlapping part . Because their last one is the same . Let's subtract this part .
  • therefore , The final state transition equation is as follows ：$dp[i+1]=dp[i]\ast 2-dp[last[s[i]]]$

class Solution {
    
public:
    int distinctSubseqII(string s) {
    
        int n = s.size();
        int MOD = 1000000007;
        if(n == 0){
    
            return 0;
        }
        
        std::vector<int> dp(n + 1);
        std::vector<int> last(26, -1);

        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
    
            dp[i + 1] = dp[i] * 2 % MOD;
            if(last[s[i] - 'a'] >= 0){
    
                dp[i + 1] -= dp[last[s[i] - 'a']];
            }
            dp[i + 1] %= MOD;
            last[s[i] - 'a'] = i;
        }

        //  Finally, remove the empty string 
        return (dp[n] - 1 + MOD) % MOD;
    }
};