Number of Unique Good Subsequences

Hard

Asked by:

16 views

Topics:

StringsDynamic Programming

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.

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 <= 10⁵
binary consists of only '0's and '1's.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the input string 's'? What is the maximum possible length of 's'?
Can the input string 's' contain characters other than '0' and '1'?
Does an empty string have any 'good subsequences'? If so, what should I return?
Is '0' a good subsequence? Is '1' a good subsequence?
Are leading zeros allowed in a subsequence? For example, is '01' considered a different good subsequence from '1'?

Brute Force Solution

Approach

The brute force approach involves generating every single possible subsequence from the given sequence. Then, we check if each subsequence is "good" based on the problem's definition. Finally, we count only the unique "good" subsequences.

Here's how the algorithm would work step-by-step:

Start by creating all possible subsequences of the original sequence.
To do this, consider each element and decide whether to include it or exclude it from the current subsequence being built.
For each subsequence you create, check if it's considered "good" according to the rules.
If a subsequence is "good", add it to a list of "good" subsequences, but only if it isn't already in the list.
Once you've gone through all possible subsequences, count how many unique "good" subsequences you have found.
That final count is the answer.

Code Implementation

def number_of_unique_good_subsequences_brute_force(sequence):
    all_subsequences = set()

    def generate_subsequences(index, current_subsequence):
        # Base case: when we have processed all elements
        if index == len(sequence):
            if current_subsequence:
                all_subsequences.add(tuple(current_subsequence))
            return

        # Exclude the current element
        generate_subsequences(index + 1, current_subsequence)

        # Include the current element
        generate_subsequences(index + 1, current_subsequence + [sequence[index]])

    generate_subsequences(0, [])

    good_subsequences = set()

    # Iterate through each subsequence
    for subsequence_tuple in all_subsequences:
        subsequence = list(subsequence_tuple)
        is_good = True
        # A sequence is not good if it starts with zero
        if subsequence[0] == 0:
            is_good = False

        if is_good:
            good_subsequences.add(tuple(subsequence))

    # We must consider the '0' case as a valid sequence.
    number_unique_good_subsequences = len(good_subsequences)

    # Add 1 if the original sequence contained zero.
    if 0 in sequence:
        number_unique_good_subsequences += 1

    return number_unique_good_subsequences

Big(O) Analysis

Time Complexity

O(2^n * n) – Generating all possible subsequences of a sequence of length n takes O(2^n) time because each element can either be included or excluded. For each subsequence generated, we need to check if it is a 'good' subsequence and if it's unique. Checking if a subsequence is 'good' and if it's unique in a list of subsequences each requires at most O(n) time, where n is the length of the original sequence because the subsequence could have at most n elements. Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(2^N) – The algorithm generates all possible subsequences, potentially 2^N in number, where N is the length of the input sequence. It stores these subsequences in a list to check for uniqueness, meaning the auxiliary space scales linearly with the maximum number of subsequences. Furthermore, the algorithm stores 'good' subsequences for checking uniqueness, which can grow up to 2^N in the worst case. Therefore, the auxiliary space required is O(2^N).

Optimal Solution

Approach

The goal is to count special sequences of digits within a given sequence, considering that a special sequence must only contain '1's and '0's, and must have a unique value. To avoid recounting sequences that represent the same value, we'll build the count gradually by including each digit and updating a running total of the number of unique values we've seen.

Here's how the algorithm would work step-by-step:

Start with a count of zero, since at the start we haven't found any special sequences yet.
Look at each digit in the given sequence from left to right.
For each '1' digit we see, double the current count of special sequences and add 1. This is because adding '1' to each existing special sequence creates a new unique sequence, and '1' itself represents one more unique sequence.
For each '0' digit we see, double the current count. But only add 1 if we haven't encountered a '0' digit before. This makes sure we don't recount a sequence of all '0's, as '0' only adds a unique special sequence the first time it's seen.
Because the counts can get very large, we need to take the remainder after dividing by a big number (like 1,000,000,007) to keep the numbers manageable.
At the very end, return the total number of unique special sequences we found by following these steps.

Code Implementation

def number_of_unique_good_subsequences(binary_string):
    modulo = 1000000007
    unique_sequences_count = 0
    seen_zero = False

    for digit in binary_string:
        if digit == '1':
            # Doubling the count and adding 1 for '1'
            unique_sequences_count = (unique_sequences_count * 2 + 1) % modulo

        elif digit == '0':
            #Doubling the count for '0'
            unique_sequences_count = (unique_sequences_count * 2) % modulo

            # Only add 1 for '0' if it's the first '0' we've seen.
            if not seen_zero:
                unique_sequences_count = (unique_sequences_count + 1) % modulo
                seen_zero = True

    return unique_sequences_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input sequence of digits once. For each digit, it performs a constant number of operations: either doubling the count and potentially adding 1 if the digit is '1', or doubling the count and conditionally adding 1 if the digit is '0' and it's the first time seeing a '0'. Therefore, the runtime is directly proportional to the length of the input sequence, which we denote as n, making the time complexity O(n).

Space Complexity

O(1) – The algorithm uses a single integer variable, count, to store the number of unique special sequences. The operations in the algorithm only involve updating this count based on the input digits. No auxiliary data structures like arrays, lists, or hashmaps are used. Therefore, the space required is constant and independent of the input sequence's length N.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 since there are no subsequences possible.
String containing only '0's	Return 1, as '0' is the only valid subsequence.
String containing only '1's	Return 1, as '1' is the only valid subsequence.
String with length 1	Return 1 if the single character is valid (either '0' or '1'), otherwise return 0.
String with leading zeros	The dynamic programming solution will correctly consider subsequences starting with '0'.
Very long string (potential for integer overflow)	Use modulo operator (%) with a prime number during calculation to prevent integer overflow.
String with repeating subsequences	The dynamic programming approach ensures unique subsequences are counted.
String contains both '0' and '1'	The dynamic programming solution accounts for both '0' and '1' and their possible combinations.

Null or empty input string

How to Handle:

Return 0 since there are no subsequences possible.

String containing only '0's

How to Handle:

Return 1, as '0' is the only valid subsequence.

String containing only '1's

How to Handle:

Return 1, as '1' is the only valid subsequence.

String with length 1

How to Handle:

Return 1 if the single character is valid (either '0' or '1'), otherwise return 0.

String with leading zeros

How to Handle:

The dynamic programming solution will correctly consider subsequences starting with '0'.

Very long string (potential for integer overflow)

How to Handle:

Use modulo operator (%) with a prime number during calculation to prevent integer overflow.

String with repeating subsequences

How to Handle:

The dynamic programming approach ensures unique subsequences are counted.

String contains both '0' and '1'

How to Handle:

The dynamic programming solution accounts for both '0' and '1' and their possible combinations.