Skip to main content
Talentd

Number of Unique Good Subsequences - Solution & Explanation

HardStringDynamic Programming19 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 <= 105
  • binary consists 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.

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'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the binary string.
Space Complexity: O(1), using constant extra space.

Try this approach in the editor →

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.

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'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the binary string.
Space Complexity: O(1), relying on constant space.

Try this approach in the editor →

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 append c to the f and g distinct good subsequences, so update g = (g + f) bmod (10^9 + 7);
  • If 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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Dynamic Programming

Time Complexity: O(n), where n is the length of the binary string.
Space Complexity: O(1), using constant extra space.

Approach 2: Bit Manipulation and Union-Find

Time Complexity: O(n), where n is the length of the binary string.
Space Complexity: O(1), relying on constant space.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 DeduplicationO(n α(n))O(n)Useful when modeling subsequence states explicitly and merging duplicates structurally

Video Solution

LeetCode 1987. Number of Unique Good Subsequences • Happy Coding • 4,783 views views

Watch 3 more video solutions →

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.

Ready to solve this problem?

Practice Number of Unique Good Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Distinct Subsequences

Next

Distinct Subsequences II