Number of Unique Good Subsequences - Practice Coding Problems

Number of Unique Good Subsequences - 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 10⁹ + 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.

Input & Output

Example 1 — Basic Binary String

$ Input: binary = "001"

› Output: 2

💡 Note: All subsequences: ["0", "0", "1", "00", "01", "01", "001"]. Good subsequences: ["0", "0", "1"]. Unique good subsequences: ["0", "1"] = 2

Example 2 — Only Ones

$ Input: binary = "11"

› Output: 3

💡 Note: All subsequences: ["1", "1", "11"]. All are good and unique count is: ["1", "11"] = 2. Wait, let me recalculate: unique subsequences are "1" and "11" = 2. Actually 3 because we have two different "1"s, but unique gives us "1" and "11" only.

Example 3 — Single Zero

$ Input: binary = "0"

› Output: 1

💡 Note: Only one subsequence: "0", which is good. Result = 1

Constraints

1 ≤ binary.length ≤ 10⁵
binary[i] is either '0' or '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with 0s and 1s

Process

Find subsequences without leading zeros (except '0')

Output

Count of unique good subsequences

Key Takeaway

🎯 Key Insight: Use DP to count by ending character rather than generating all subsequences

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use dynamic programming to track subsequences by their ending character, avoiding the need to generate all subsequences. The optimal approach handles the special case of '0' separately and counts subsequences starting with '1' using the formula: count = count × 2 + 1 for each '1' encountered. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n)	O(1)	Track subsequences ending with 0 and 1 to avoid duplicates
Generate All Subsequences	O(2ⁿ × n)	O(2ⁿ × n)	Generate all possible subsequences and count unique good ones
Optimized DP with Special Zero Handling	O(n)	O(1)	Enhanced DP approach that properly handles the special '0' case

Dynamic Programming — Algorithm Steps

Initialize counts for subsequences ending with 0 and 1
For each character, update counts based on previous counts
Handle special case for single '0' subsequence

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with zero counts for subsequences ending with 0 and 1

Process Each Character

Update counts based on current character

Sum Counts

Total unique good subsequences

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

#define MOD 1000000007

int solution(char* binary) {
    int n = strlen(binary);
    
    // Count subsequences ending with 0 and 1
    long long endsWithZero = 0;
    long long endsWithOne = 0;
    
    for (int i = 0; i < n; i++) {
        char c = binary[i];
        if (c == '0') {
            // Any subsequence ending with 1 can now end with 0
            // Plus the single '0' subsequence
            endsWithZero = (endsWithOne + 1) % MOD;
        } else { // c == '1'
            // Any existing subsequence can now end with 1
            // Plus the single '1' subsequence
            endsWithOne = (endsWithZero + endsWithOne + 1) % MOD;
        }
    }
    
    return (endsWithZero + endsWithOne) % MOD;
}

int main() {
    char binary[1001];
    fgets(binary, sizeof(binary), stdin);
    binary[strcspn(binary, "\n")] = 0;
    
    int result = solution(binary);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string with constant work per character

✓ Linear Growth

Space Complexity

O(1)

Only storing two counters for subsequences ending with 0 and 1

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler