1987. Number of Unique Good Subsequences LeetCode Solution
In this guide, you will get 1987. Number of Unique Good Subsequences LeetCode Solution with the best time and space complexity. The solution to Number of Unique Good Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Unique Good Subsequences
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”.
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 <= 105
binary consists of only '0's and '1's.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1987. Number of Unique Good Subsequences LeetCode Solution in C++
class Solution {
public:
// Similar to 940. Distinct Subsequences II
int numberOfUniqueGoodSubsequences(string binary) {
constexpr int kMod = 1'000'000'007;
// endsIn[i] := the number of subsequence that end in ('0' + i)
vector<int> endsIn(2);
for (const char c : binary) {
endsIn[c - '0'] = (endsIn[0] + endsIn[1]) % kMod;
// Don't count '0' since we want to avoid the leading zeros case.
// However, we can always count '1'.
if (c == '1')
++endsIn[1];
}
// Count '0' in the end.
return (endsIn[0] + endsIn[1] +
(binary.find('0') == string::npos ? 0 : 1)) %
kMod;
}
}; /* code provided by PROGIEZ */
1987. Number of Unique Good Subsequences LeetCode Solution in Java
class Solution {
// Similar to 940. Distinct Subsequences II
public int numberOfUniqueGoodSubsequences(String binary) {
final int kMod = 1_000_000_007;
// endsIn[i] := the number of subsequence that end in ('0' + i)
int[] endsIn = new int[2];
for (final char c : binary.toCharArray()) {
endsIn[c - '0'] = (endsIn[0] + endsIn[1]) % kMod;
// Don't count '0' since we want to avoid the leading zeros case.
// However, we can always count '1'.
if (c == '1')
++endsIn[1];
}
// Count '0' in the end.
return (endsIn[0] + endsIn[1] + (binary.indexOf('0') == -1 ? 0 : 1)) % kMod;
}
} // code provided by PROGIEZ
1987. Number of Unique Good Subsequences LeetCode Solution in Python
class Solution:
# Similar to 940. Distinct Subsequences II
def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
kMod = 1_000_000_007
# endsIn[i] := the number of subsequence that end in ('0' + i)
endsIn = {'0': 0, '1': 0}
for c in binary:
endsIn[c] = sum(endsIn.values()) % kMod
# Don't count '0' since we want to avoid the leading zeros case.
# However, we can always count '1'.
if c == '1':
endsIn['1'] += 1
# Count '0' in the end.
return (sum(endsIn.values()) + ('0' in binary)) % kMod # code by PROGIEZ
