You are given a binary string binary. A subsequence of binary is considered good if it is not empty and has no leading zeros (with the exception of "0").
Find the number of unique good subsequences of binary.
- For example, if
binary = "001", then all the good subsequences are["0", "0", "1"], so the unique good subsequences are"0"and"1". Note that subsequences"00","01", and"001"are not good because they have leading zeros.
Return the number of unique good subsequences of binary. Since the answer may be very large, return it modulo 109 + 7.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: binary = "001" Output: 2 Explanation: The good subsequences of binary are ["0", "0", "1"]. The unique good subsequences are "0" and "1".
Example 2:
Input: binary = "11" Output: 2 Explanation: The good subsequences of binary are ["1", "1", "11"]. The unique good subsequences are "1" and "11".
Example 3:
Input: binary = "101" Output: 5 Explanation: The good subsequences of binary are ["1", "0", "1", "10", "11", "101"]. The unique good subsequences are "0", "1", "10", "11", and "101".
Constraints:
1 <= binary.length <= 105binaryconsists of only'0's and'1's.
Related Topics:
String, Dynamic Programming
Similar Questions:
Let dp[i+1] be the number of unique good subsequences, including empty subsequence, in s[0..i]. The anwer is dp[N] - 1 (-1 to remove the empty sequence)
Let dp[0] = 1 representing a empty subsequence.
Step 1. Multiplying by 2:
For dp[i+1], we can start by appending s[i] to all subsequences represented by dp[i], so dp[i+1] starts from 2 * dp[i].
For example, assume s = "111", and dp[2] = 3 represending nil, 1, 11. We can append s[2] = 1 to them and get 1, 11, 111. So dp[i+1] starts from 2 * dp[2] = 6 represending nil, 1, 11 plus 1, 11, 111.
Step 2. Deduplication:
Assume the last time we saw s[i] value was at index j. So dp[j] reprensents all the unique good subsequences in s[0..(j-1)]. This number of subsequences are counted twice in our previous computation because these subsequences ending with s[j] or s[i] yields the same set of subsequences.
For the above example, when computing dp[3], we counted dp[1] = 2 number of subsequences twice. dp[1] represents nil, 1. Appending s[1] = 1 or s[2] = 1 will get the same subsequences -- 1, 11.
To dedup, we do dp[i+1] = 2 * dp[i] - dp[j].
One caveat is that if dp[j] contains 0 subsequence, we can't append it to either s[i] or s[j]. So instead of - dp[j], we should - (dp[j] - zero[j]) where zero[j] = 1 if we've seen 0 in s[0..(j-1)]; otherwise zero[j] = 0.
We can store this dp[j] - zero[j] in dup[0] and dup[1] respectively.
So, dp[i+1] = 2 * dp[i] - dup[s[i]-'0'].
Step 3. Remove leading zero:
Lastly, if dp[i] includes subsequence 0, we can't append s[i] to it. So we need to - zero[i].
Finally, dp[i+1] = 2 * dp[i] - dup[s[i]-'0'] - zero[i].
In implementation, since dp[i+1] only depends on dp[i], and zero[i] just means if we have seen 0 before -- zero[i] = dup[0] > 0, we can using a single value to track the dp values.
// OJ: https://leetcode.com/problems/number-of-unique-good-subsequences/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numberOfUniqueGoodSubsequences(string s) {
long mod = 1e9 + 7, dup[2] = {}, ans = 1;
for (char c : s) {
int prev = ans, zero = dup[0] > 0;
ans = (2 * ans - dup[c - '0'] - zero + mod) % mod;
dup[c - '0'] = prev - zero;
}
return (ans - 1 + mod) % mod;
}
};// OJ: https://leetcode.com/problems/number-of-unique-good-subsequences/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/number-of-unique-good-subsequences/discuss/1431819/JavaC%2B%2BPython-DP-4-lines-O(N)-Time-O(1)-Space
class Solution {
public:
int numberOfUniqueGoodSubsequences(string s) {
long mod = 1e9 + 7, cnt[2] = {};
for (char c : s) cnt[c - '0'] = (cnt[0] + cnt[1] + c - '0') % mod;
return (cnt[0] + cnt[1] + (s.find('0') != string::npos)) % mod;
}
};