Count the Number of Good Subsequences

Medium

Palantir

11 views

Topics:

ArraysTwo PointersSliding Windows

You are given a binary string s. A subsequence of s is considered good if it is not empty and has a value that is a power of 5.

For example, if s = "1011", then "1", "11", "101", and "1011" are some of its subsequences. Among these, only the subsequence "101" has a value of 5, which is a power of 5.

Return the number of good subsequences in s. Since the answer may be large, return it modulo 10⁹ + 7.

A subsequence of a string is formed by deleting some characters (possibly none) of the string.
The value of a string is its decimal representation.
For example, if s = "101", then its value is 5.

Example 1:

Input: s = "000"
Output: 0
Explanation: There are no good subsequences, so we return 0.

Example 2:

Input: s = "1011"
Output: 5
Explanation: The good subsequences are "1", "1", "101", "11", and "1011".

Example 3:

Input: s = "0110"
Output: 2
Explanation: The good subsequences are "10" and "10".

Constraints:

1 <= s.length <= 10⁴
s[i] is either '0' or '1'.

Try coding it in LeetCode

Count the Number of Good Subsequences

Medium

Palantir

11 views

Topics:

ArraysTwo PointersSliding Windows

You are given a binary string s. A subsequence of s is considered good if it is not empty and has a value that is a power of 5.

For example, if s = "1011", then "1", "11", "101", and "1011" are some of its subsequences. Among these, only the subsequence "101" has a value of 5, which is a power of 5.

Return the number of good subsequences in s. Since the answer may be large, return it modulo 10⁹ + 7.

A subsequence of a string is formed by deleting some characters (possibly none) of the string.
The value of a string is its decimal representation.
For example, if s = "101", then its value is 5.

Example 1:

Input: s = "000"
Output: 0
Explanation: There are no good subsequences, so we return 0.

Example 2:

Input: s = "1011"
Output: 5
Explanation: The good subsequences are "1", "1", "101", "11", and "1011".

Example 3:

Input: s = "0110"
Output: 2
Explanation: The good subsequences are "10" and "10".

Constraints:

1 <= s.length <= 10⁴
s[i] is either '0' or '1'.

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 is the maximum size of the input sequence?
Can the input sequence contain negative numbers, zeros, or floating point numbers?
What defines a "good subsequence" precisely? Are there any specific criteria or properties it must satisfy that aren't explicitly stated?
Are duplicate numbers allowed within the input sequence, and how should they be handled when determining if a subsequence is "good"?
If no good subsequences exist, what should the function return? Should it return 0, -1, null, or throw an exception?

Brute Force Solution

Approach

The brute force approach involves checking every possible subsequence in the given input. We'll examine each subsequence individually to see if it satisfies a certain property that defines a 'good' subsequence. By checking everything, we guarantee we'll find all the good ones.

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

First, consider the subsequence that includes only the first element from the input.
Then, consider the subsequence that includes only the second element, and so on, until you've considered each element individually as a subsequence.
Next, consider all subsequences that include two elements, starting with the first two elements, then the first and third, and so on, until you've considered every possible pair.
Continue this process, building up subsequences of increasing length (three elements, four elements, and so on), always considering all possible combinations of elements.
For each subsequence you create, check if it meets the criteria to be considered a 'good' subsequence.
If a subsequence is 'good', increment a counter.
After you have considered all possible subsequences, the value of the counter will be the total number of 'good' subsequences.

Code Implementation

def count_good_subsequences_brute_force(sequence):
    list_length = len(sequence)
    good_subsequence_count = 0

    # Iterate through all possible subsequences
    for i in range(1 << list_length):
        subsequence = []
        for j in range(list_length):
            # Check if the j-th element is included in the subsequence
            if (i >> j) & 1:
                subsequence.append(sequence[j])

        #Now we are calling the 'is_good' function to check
        #if it is a valid subsequence and increment
        if is_good_subsequence(subsequence):
            good_subsequence_count += 1

    return good_subsequence_count

def is_good_subsequence(subsequence):
    # This is a placeholder; replace with your 'good' criteria
    # Currently, it makes any non-empty subsequence 'good'
    return len(subsequence) > 0

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm iterates through all possible subsequences of the input. For an input of size n, there are 2^n possible subsequences (each element can either be included or excluded). For each of these subsequences, we perform a check to determine if it is a 'good' subsequence, which takes O(1) time. Therefore, the overall time complexity is proportional to the number of subsequences, which is O(2^n).

Space Complexity

O(1) – The provided brute force approach iterates through subsequences and checks if each one is 'good'. It does not explicitly mention storing all subsequences. The plain english explanation suggests a counter and iterative comparisons within nested loops, implying no significant auxiliary data structures are created or stored. Thus, the space complexity is dominated by a few counter variables, whose memory footprint is constant regardless of the input size, N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks to find how many subsequences of a given sequence meet a specific condition. Instead of checking all possible subsequences individually, we can use a more efficient method that builds up the answer step-by-step, leveraging previous calculations to avoid redundant work. The key idea is to count the number of valid subsequences ending at each position in the sequence.

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

First, understand that a subsequence doesn't need to be continuous; it just needs to keep the same order as the original sequence.
Imagine building valid subsequences one element at a time, starting from the beginning of the original sequence.
Keep track of the number of valid subsequences you've found so far that end with each possible value.
When you consider a new element from the original sequence, look at all the valid subsequences you've already found.
If the new element can extend any of those existing valid subsequences to form an even longer valid subsequence, update the count of valid subsequences ending with the new element.
The specific update will be based on the rules the valid subsequences need to meet (defined in the problem description).
After processing all the elements of the original sequence, add up the counts of all the valid subsequences you tracked along the way. The total will be the answer.

Code Implementation

def count_good_subsequences(sequence):
    ends_with_counts = {}

    for element in sequence:
        # Store counts of subsequences before update.
        previous_counts = ends_with_counts.copy()

        # Add 'element' to existing subsequences.
        for value, count in previous_counts.items():
            if element > value:
                ends_with_counts[element] = ends_with_counts.get(element, 0) + count

        # Initialize if 'element' creates a new subsequence.
        ends_with_counts[element] = ends_with_counts.get(element, 0) + 1

    # Sum all counts for total good subsequences
    total_subsequences = sum(ends_with_counts.values())
    return total_subsequences

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through each of the n elements in the input sequence. For each element, it potentially updates the counts of valid subsequences. Updating the counts involves looking at existing valid subsequences and extending them. If there are k possible values that could end a valid subsequence (where k is not dependent on n), updating the counts for a particular value involves a single operation, for k possible values. This makes the total complexity O(n*k).

Space Complexity

O(K) – The explanation indicates we are 'keeping track of the number of valid subsequences you've found so far that end with each possible value'. This implies we are storing counts associated with distinct values encountered in the input sequence. In the worst case, all N elements are distinct. However the solution will keep track of valid subsequence count which end with 'each possible value'. Let's say number of possible values in the input sequence is K. Therefore we would need to store at most K counts. Thus, the auxiliary space complexity is O(K) where K is the number of distinct possible values.

Edge Cases

Case	How to Handle
Empty input array	Return 0 as there are no subsequences.
Array with a single element	Return 0 as a subsequence needs at least one character
Input array contains only zeros	The count should accurately reflect the number of subsequences that sum to a multiple of the divisor
Large input array with large numbers, potential overflow during sum	Use modulo arithmetic during summation to prevent integer overflow if intermediate sums can get very large.
Input array containing negative numbers	The algorithm should handle negative numbers correctly by considering their contribution to the sum and subsequence count.
Large input array with divisor being a large number.	Modulo operation should be performed carefully with large numbers involved.
All elements in the array are the same	Ensure combination calculations avoid redundancy.
Divisor is zero	Throw an exception or return an error code as division by zero is undefined.