Number of Unique Good Subsequences solution and explanation
Google
3 more videos on this problem
LeetCode 1987. Number of Unique Good SubsequencesHappy Coding · 18:02 · 4K views
1987. Number of Unique Good Subsequences (Leetcode Hard)Programming Live with Larry · 1:24:34 · 1K views
【每日一题】LeetCode 1987. Number of Unique Good SubsequencesHuifeng Guan · 13:16 · 412 views
LeetCode 1987: Number of Unique Good SubsequencesAlitaCode · 26:45 · 54 views
The problem
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.
Approach overview
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.
Approach 1: Approach 1: Dynamic Programming
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.
def count_unique_good_subsequences(binary: str) -> int:
MOD = 1000000007
dp = [0, 0] # dp[0] for ending with '0', dp[1] for ending with '1'
contains_zero = False
for char in binary:
if char == '0':
contains_zero = True
dp[0] = (dp[0] + dp[1]) % MOD
else: # char == '1'
dp[1] = (dp[0] + dp[1] + 1) % MOD
return (dp[0] + dp[1] + (1 if contains_zero else 0)) % MOD
binary = "001"
print(count_unique_good_subsequences(binary))public class UniqueGoodSubsequences {
public int countUniqueGoodSubsequences(String binary) {
final int MOD = 1000000007;
int[] dp = new int[2]; // For ending with '0' and ending with '1'
boolean containsZero = false;
for (char c : binary.toCharArray()) {
if (c == '0') {
containsZero = true;
dp[0] = (dp[0] + dp[1]) % MOD;
} else { // '1'
dp[1] = (dp[0] + dp[1] + 1) % MOD;
}
}
return (dp[0] + dp[1] + (containsZero ? 1 : 0)) % MOD;
}
public static void main(String[] args) {
UniqueGoodSubsequences ugs = new UniqueGoodSubsequences();
String binary = "001";
System.out.println(ugs.countUniqueGoodSubsequences(binary));
}
}#include <iostream>
#include <string>
using namespace std;
#define MOD 1000000007
int countUniqueGoodSubsequences(string binary) {
int dp[2] = {0, 0}; // For ending with '0' and '1'
bool contains_zero = false;
for (char c : binary) {
if (c == '0') {
contains_zero = true;
dp[0] = (dp[0] + dp[1]) % MOD;
} else { // '1'
dp[1] = (dp[0] + dp[1] + 1) % MOD;
}
}
return (dp[0] + dp[1] + contains_zero) % MOD;
}
int main() {
string binary = "001";
cout << countUniqueGoodSubsequences(binary) << endl;
return 0;
}function countUniqueGoodSubsequences(binary) {
const MOD = 1000000007;
let dp = [0, 0]; // For ending with '0' and '1'
let containsZero = false;
for (let char of binary) {
if (char === '0') {
containsZero = true;
dp[0] = (dp[0] + dp[1]) % MOD;
} else { // '1'
dp[1] = (dp[0] + dp[1] + 1) % MOD;
}
}
return (dp[0] + dp[1] + (containsZero ? 1 : 0)) % MOD;
}
let binary = "001";
console.log(countUniqueGoodSubsequences(binary));#include <stdio.h>
#define MOD 1000000007
int countUniqueGoodSubsequences(char *binary) {
int dp[2] = {0, 0}; // dp[0] for ending with '0', dp[1] for ending with '1'
int contains_zero = 0;
for (int i = 0; binary[i] != '\0'; i++) {
if (binary[i] == '0') {
contains_zero = 1;
dp[0] = (dp[0] + dp[1]) % MOD;
} else if (binary[i] == '1') {
dp[1] = (dp[0] + dp[1] + 1) % MOD;
}
}
return (dp[0] + dp[1] + contains_zero) % MOD;
}
int main() {
char binary[] = "001";
printf("%d\n", countUniqueGoodSubsequences(binary));
return 0;
}using System;
public class UniqueGoodSubsequences {
public static int CountUniqueGoodSubsequences(string binary) {
const int MOD = 1000000007;
int[] dp = new int[2]; // For ending with '0' and '1'
bool containsZero = false;
foreach (char c in binary) {
if (c == '0') {
containsZero = true;
dp[0] = (dp[0] + dp[1]) % MOD;
} else { // '1'
dp[1] = (dp[0] + dp[1] + 1) % MOD;
}
}
return (dp[0] + dp[1] + (containsZero ? 1 : 0)) % MOD;
}
public static void Main() {
string binary = "001";
Console.WriteLine(CountUniqueGoodSubsequences(binary));
}
}Utilizing Python, we manage subsequence counts using a list dp. The subsequence status depends on the character encounters ('0' or '1'), updated accordingly with conditions to track valid sequence counts. A boolean contains_zero is used to include lone '0' if it's present.
Time Complexity: O(n), where n is the length of the binary string.
Space Complexity: O(1), using constant extra space.
Approach 2: Approach 2: Bit Manipulation and Union-Find
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.
def count_unique_good_subsequences(binary: str) -> int:
MOD = 1000000007
bit_count = [0, 0]
union_find = 0
for char in binary:
bit = int(char)
bit_count[bit] = (bit_count[0] + bit_count[1] + (1 if bit == 1 else 0)) % MOD
union_find |= (1 << bit)
result = (bit_count[0] + bit_count[1]) % MOD
if union_find & 1:
result = (result + 1) % MOD
return result
print(count_unique_good_subsequences("101"))public class UniqueGoodSubsequences {
public int countUniqueGoodSubsequences(String binary) {
final int MOD = 1000000007;
int[] bitCount = new int[2];
int unionFind = 0;
for (char c : binary.toCharArray()) {
int bit = c - '0';
bitCount[bit] = (bitCount[0] + bitCount[1] + (bit == 1 ? 1 : 0)) % MOD;
unionFind |= (1 << bit);
}
int result = (bitCount[0] + bitCount[1]) % MOD;
if ((unionFind & 1) == 1) {
result = (result + 1) % MOD;
}
return result;
}
public static void main(String[] args) {
UniqueGoodSubsequences ugs = new UniqueGoodSubsequences();
System.out.println(ugs.countUniqueGoodSubsequences("101"));
}
}#include <iostream>
#include <string>
using namespace std;
#define MOD 1000000007
int countUniqueGoodSubsequences(string binary) {
int bitCount[2] = {0};
int unionFind = 0;
for (char c : binary) {
int bit = c - '0';
bitCount[bit] = (bitCount[0] + bitCount[1] + (bit == 1 ? 1 : 0)) % MOD;
unionFind |= (1 << bit);
}
int result = (bitCount[0] + bitCount[1]) % MOD;
if (unionFind & 1) {
result = (result + 1) % MOD;
}
return result;
}
int main() {
cout << countUniqueGoodSubsequences("101") << endl;
return 0;
}function countUniqueGoodSubsequences(binary) {
const MOD = 1000000007;
let bitCount = [0, 0]; // For '0' and '1'
let unionFind = 0;
for (let char of binary) {
let bit = parseInt(char);
bitCount[bit] = (bitCount[0] + bitCount[1] + (bit === 1 ? 1 : 0)) % MOD;
unionFind |= (1 << bit);
}
let result = (bitCount[0] + bitCount[1]) % MOD;
if (unionFind & 1) {
result = (result + 1) % MOD;
}
return result;
}
console.log(countUniqueGoodSubsequences("101"));#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int countUniqueGoodSubsequences(char *binary) {
int bitCount[2] = {0};
int len = strlen(binary);
int unionFind = 0;
for (int i = 0; i < len; i++) {
int currentBit = binary[i] - '0';
bitCount[currentBit] = (bitCount[0] + bitCount[1] + (currentBit == 1 ? 1 : 0)) % MOD;
unionFind |= (1 << currentBit);
}
int result = (bitCount[0] + bitCount[1]) % MOD;
if (unionFind & 1) {
result = (result + 1) % MOD;
}
return result;
}
int main() {
char binary[] = "101";
printf("%d\n", countUniqueGoodSubsequences(binary));
return 0;
}using System;
public class UniqueGoodSubsequences {
public static int CountUniqueGoodSubsequences(string binary) {
const int MOD = 1000000007;
int[] bitCount = new int[2];
int unionFind = 0;
foreach (char c in binary) {
int bit = c - '0';
bitCount[bit] = (bitCount[0] + bitCount[1] + (bit == 1 ? 1 : 0)) % MOD;
unionFind |= (1 << bit);
}
int result = (bitCount[0] + bitCount[1]) % MOD;
if ((unionFind & 1) != 0) {
result = (result + 1) % MOD;
}
return result;
}
public static void Main() {
Console.WriteLine(CountUniqueGoodSubsequences("101"));
}
}Utilizing Python, the solution employs a bit_count array to manage subsequence options and a union_find bitmask to track when subsequences such as solely '0' should be included in the count.
Time Complexity: O(n), where n is the input string length.
Space Complexity: O(1), constant space usage.
Approach 3: Dynamic Programming
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:
- If
c = 0, we can appendcto thefandgdistinct good subsequences, so updateg = (g + f) bmod (10^9 + 7); - If
c = 1, we can appendcto thefandgdistinct good subsequences, and also appendcalone, so updatef = (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:
function numberOfUniqueGoodSubsequences(binary: string): number {
let [f, g] = [0, 0];
let ans = 0;
const mod = 1e9 + 7;
for (const c of binary) {
if (c === '0') {
g = (g + f) % mod;
ans = 1;
} else {
f = (f + g + 1) % mod;
}
}
ans = (ans + f + g) % mod;
return ans;
}func numberOfUniqueGoodSubsequences(binary string) (ans int) {
const mod int = 1e9 + 7
f, g := 0, 0
for _, c := range binary {
if c == '0' {
g = (g + f) % mod
ans = 1
} else {
f = (f + g + 1) % mod
}
}
ans = (ans + f + g) % mod
return
}Complexity comparison
| 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 input string length. |
| Dynamic Programming | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Number of Unique Good Subsequences easy or hard?
LeetCode classifies this problem as Hard because it combines subsequence counting, duplicate elimination, and constraints around leading zeros. The difficulty comes from recognizing that only two dynamic states are required instead of enumerating all subsequences.
Number of Unique Good Subsequences Python/Java solution
Python and Java implementations typically maintain two variables: one for subsequences ending in '0' and one for those ending in '1'. As the string is scanned, these values are updated using modular arithmetic to prevent overflow. The algorithm stays O(n) in time and O(1) in space across languages.
How to solve Number of Unique Good Subsequences in O(n)?
Scan the binary string once while maintaining counts of unique subsequences ending with '0' and '1'. When encountering '1', extend all existing subsequences and start a new one. When encountering '0', only extend subsequences that already started with '1', while separately tracking whether a standalone '0' exists. This produces the final count in linear time.
What is the best approach for Number of Unique Good Subsequences?
The optimal solution uses dynamic programming with two counters that track unique subsequences ending in 0 and 1. While iterating through the binary string, each character updates these states based on valid transitions. This avoids generating subsequences explicitly and runs in O(n) time with O(1) extra space.
Is Number of Unique Good Subsequences asked at Google/Amazon/Meta?
Hard dynamic programming problems involving subsequences and deduplication frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require counting unique subsequences under constraints are common because they test state design and optimization skills.
What data structure is used in Number of Unique Good Subsequences?
The main solution relies on dynamic programming state variables rather than complex data structures. Some conceptual variants model subsequence states using sets or disjoint-set unions for deduplication, but the optimal implementation only needs integer counters and modular arithmetic.
What is the time complexity of Number of Unique Good Subsequences?
The optimal dynamic programming solution runs in O(n) time, where n is the length of the binary string. Each character triggers constant-time updates to two state variables. Space complexity is O(1) since only a few counters and flags are maintained.