Number of Unique Good Subsequences - Video Solutions

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.