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.
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 <= 105binary consists of only '0's and '1's.Problem Overview: Given a binary string, count the number of unique good subsequences. A subsequence is good if it has no leading zeros unless the subsequence itself is "0". Duplicate subsequences must be counted once, which turns the problem into a combination of subsequence generation and deduplication.
Approach 1: Dynamic Programming (O(n) time, O(1) space)
The key observation: every good subsequence must end with either 0 or 1. Track two counters while scanning the string from left to right: the number of unique subsequences ending in 0 and those ending in 1. When you see a 1, it can extend all existing subsequences or start a new one, so update the endWith1 count. When you see a 0, it can only extend existing subsequences that already started with 1, because leading zeros are not allowed except for the single "0" subsequence. Maintain a flag to record whether a standalone "0" exists. Each step performs constant updates, giving O(n) time and O(1) extra space. This approach relies on careful state transitions typical in dynamic programming and works directly on the string without generating subsequences explicitly.
Approach 2: Bit Manipulation and Union-Find (O(n α(n)) time, O(n) space)
This perspective treats each subsequence state as a node representing the binary value pattern formed so far. Bit manipulation helps encode subsequence endings compactly, while a Union-Find structure merges states that represent identical subsequences created through different index paths. During iteration, extending a subsequence with the next bit may produce duplicates; union operations collapse those equivalent states so only unique representatives remain. Path compression keeps the amortized cost near constant, leading to roughly O(n α(n)) time and O(n) space. The method highlights how deduplication can be handled structurally using disjoint-set unions, often paired with bit manipulation for compact state handling.
Recommended for interviews: The dynamic programming solution is what interviewers expect. It shows you can convert a subsequence counting problem into a small set of states and avoid exponential enumeration. Explaining why leading zeros restrict transitions demonstrates deeper reasoning about constraints. The alternative structural approach is interesting conceptually, but the constant-space DP is the cleanest and most efficient answer.
This approach involves using a Dynamic Programming (DP) technique to track the number of unique good subsequences ending with '0' and '1'. We will also maintain a flag to handle the special case when '0' is a valid good subsequence on its own.
We maintain an array dp where dp[0] stores the count of unique good subsequences that end with '0' and dp[1] stores those that end with '1'. We iterate through the binary string, updating these counts. If we encounter '0', potential subsequences ending with '0' increase by those ending with '1'. For '1', we derive new subsequences by appending '1' to all previous, plus the new standalone '1'. We use a flag contains_zero to account for the subsequence '0'.
Time Complexity: O(n), where n is the length of the binary string.
Space Complexity: O(1), using constant extra space.
This approach involves using bit manipulation and union-find data structure concepts to efficiently determine unique subsequences. The idea is to utilize bitwise operations to track uniquely formable subsequences.
In this C implementation, we use a bit manipulation trick through the unionFind integer variable to track which characters have been included in subsequences. We iterate over the binary string updating the bitCount array based on union of new subsequences from existing ones. Finally, we check the unionFind to ensure inclusion of any standalone '0'.
Time Complexity: O(n), where n is the length of the binary string.
Space Complexity: O(1), relying on constant space.
We define f as the number of distinct good subsequences ending with 1, and g as the number of distinct good subsequences ending with 0 and starting with 1. Initially, f = g = 0.
For a binary string, we can traverse each bit from left to right. Suppose the current bit is c:
c = 0, we can append c to the f and g distinct good subsequences, so update g = (g + f) bmod (10^9 + 7);c = 1, we can append c to the f and g distinct good subsequences, and also append c alone, so update f = (f + g + 1) bmod (10^9 + 7).If the string contains 0, the final answer is f + g + 1, otherwise the answer is f + g.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | Time Complexity: O(n), where n is the length of the binary string. |
| Approach 2: Bit Manipulation and Union-Find | Time Complexity: O(n), where n is the length of the binary string. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Track subsequences ending with 0/1) | O(n) | O(1) | Best general solution for large strings; minimal memory and interview-preferred |
| Bit Manipulation + Union-Find Deduplication | O(n α(n)) | O(n) | Useful when modeling subsequence states explicitly and merging duplicates structurally |
LeetCode 1987. Number of Unique Good Subsequences • Happy Coding • 4,651 views views
Watch 4 more video solutions →Practice Number of Unique Good Subsequences with our built-in code editor and test cases.
Practice on FleetCode