1987. Number of Unique Good Subsequences

Description

image-20210831012335939

image-20210831012343334

Solution

Refer to Distinct Subsequences

We calculate the different subsequence end with ith index.

1
2
3
4
5
6
7
8
dp0[i] -> stands for from begin to ith index, subsequence number end with 0
dp1[i] -> stands for from begin to ith index, subsequence number end with 1

dp1[i] = dp1[i-1] + dp0[i-1] + 1 (for ith is 1)
dp1[i] = dp1[i-1] (for ith is 0)

dp0[i] = dp1[i-1] + dp0[i-1] (for ith is 0)
dp0[i] = dp0[i-1] (for ith is 1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    const int MOD = 1E9 + 7;
public:
    int numberOfUniqueGoodSubsequences(string binary) {
        int n = binary.size();
        vector<int> dp1(n), dp2(n);
        dp1[0] = binary[0]-'0';
        bool flag= binary[0] == '0';
        for(int i = 1; i < n; i++){
            if(binary[i] == '1'){
                dp1[i] = (dp1[i-1] + dp2[i-1] + 1)%MOD;
                dp2[i] = dp2[i-1];
            }else{
                dp1[i] = dp1[i-1];
                dp2[i] = (dp2[i-1] + dp1[i-1])%MOD;
                flag= true;
            }
            //cout << dp1[i] << " "<<dp2[i] <<endl;
        }
        return (dp1[n-1]+dp2[n-1] + flag)%MOD;
    }
};