We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Unique Good Subsequences

Difficulty: Hard

Problem Description

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. Return the result modulo 10^9 + 7.

Key Insights

  • A good subsequence is defined as any non-empty subsequence that does not start with a '0' unless it is the single character "0".
  • We can generate subsequences from the string by considering combinations of its characters.
  • The unique good subsequences can be derived from counting the occurrences of '0's and '1's in the string.
  • The presence of '1's leads to various combinations, while '0's add limited unique subsequences (only "0" itself or combinations with '1's).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), as we only need a few variables to keep track of counts.

Solution

To solve the problem, we can use a straightforward approach by counting the number of '0's and '1's in the binary string. We then derive the number of unique good subsequences based on these counts:

  1. If there are no '1's, the only good subsequence is "0".
  2. If there are '1's, we can create good subsequences from them in combination with any '0's present.
  3. The total unique good subsequences can be calculated using the formula based on the number of '1's and whether there are '0's.

Code Solutions

def uniqueGoodSubseq(binary: str) -> int:
    MOD = 10**9 + 7
    count_0 = binary.count('0')
    count_1 = binary.count('1')
    
    if count_1 == 0:
        return 1  # Only "0" is a good subsequence
    
    # Total unique good subsequences
    # 2^count_1 - 1 for all non-empty subsequences of '1's + 1 for the "0"
    result = (pow(2, count_1, MOD) - 1 + (1 if count_0 > 0 else 0)) % MOD
    return result
← Back to All Questions