Taro Logo

Longest Binary Subsequence Less Than or Equal to K

Medium
Google logo
Google
3 views
Topics:
StringsGreedy Algorithms

You are given a binary string s and a positive integer k. Return the length of the longest subsequence of s that makes up a binary number less than or equal to k. Note the following:

  1. The subsequence can contain leading zeroes.
  2. The empty string is considered to be equal to 0.
  3. A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

For example, given s = "1001010" and k = 5, the longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", which is equal to 2 in decimal. The length of this subsequence is 5, so you should return 5. Other possible subsequences are "00100" (4 in decimal) and "00101" (5 in decimal).

Another example: given s = "00101001" and k = 1, the longest subsequence of s that makes up a binary number less than or equal to 1 is "000001", which is equal to 1 in decimal. The length of this subsequence is 6, so you should return 6.

How would you approach this problem efficiently? Consider edge cases and optimize for both time and space complexity.

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:

  1. What is the range of values for both the elements in the binary string and the integer K? Should I expect negative numbers?
  2. Is the input string guaranteed to be a valid binary string (containing only '0' and '1' characters)?
  3. If there are multiple subsequences with the same maximum length that are less than or equal to K, which one should I return (any one is acceptable, or do you have a specific requirement)?
  4. What should I return if no subsequence exists that is less than or equal to K (e.g., return an empty string, null, or some other defined value)?
  5. Is K guaranteed to be non-negative?

Brute Force Solution

Approach

The goal is to find the longest combination of numbers from the binary sequence that sums up to a value less than or equal to a target value. The brute force approach involves checking every possible combination of numbers from the given sequence.

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

  1. Consider every possible group of numbers from the binary sequence. This means trying out selecting the first number only, the second number only, then the first and second, then the first and third, and so on, until all possible combinations are checked.
  2. For each of these groups, calculate the sum of the numbers.
  3. Check if the sum is less than or equal to the target value.
  4. If the sum satisfies the condition (less than or equal to target), keep track of the number of numbers in that group.
  5. After checking all possible groups, find the group with the most numbers that satisfied the condition.
  6. The number of numbers in that group represents the length of the longest subsequence.

Code Implementation

def longest_binary_subsequence_brute_force(binary_sequence, target_value):

    max_length = 0
    sequence_length = len(binary_sequence)

    # Iterate through all possible subsequences
    for i in range(1 << sequence_length):
        current_subsequence = []
        current_sum = 0
        current_length = 0

        # Construct the subsequence and calculate its sum
        for j in range(sequence_length):
            # Check if j-th bit is set in the current combination
            if (i >> j) & 1:
                current_subsequence.append(binary_sequence[j])
                current_sum += binary_sequence[j]
                current_length += 1

        # Check if the sum is less than or equal to the target
        if current_sum <= target_value:
            # Update max_length if needed
            if current_length > max_length:
                max_length = current_length

    return max_length

Big(O) Analysis

Time Complexity
O(2^n)The described approach considers every possible subsequence (group) of the input binary sequence of size n. Generating all subsequences corresponds to iterating through all possible combinations of elements, which is equivalent to the power set of the input set. The power set of a set with n elements has 2^n subsets. Therefore, the algorithm performs operations proportional to the number of subsets, giving a time complexity of O(2^n).
Space Complexity
O(1)The provided brute force approach explores every possible subsequence but does not store them explicitly. It calculates the sum for each subsequence on the fly. The only auxiliary space required is for storing a few integer variables to keep track of the current sum, the target value K, and the length of the longest subsequence found so far. These variables occupy a constant amount of space, irrespective of the input size N (the length of the binary sequence). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the longest possible sequence of ones and zeros from the input, but treating it as a binary number that is less than or equal to a given limit. Instead of trying every possible combination, we should prioritize using zeros because they contribute nothing to the overall value, and then strategically place ones where needed.

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

  1. Count the total number of zeros in the input. These zeros will always be part of the optimal subsequence because they don't increase the value.
  2. Starting from the right side (least significant bit) of the input, include as many ones as possible without exceeding the given limit.
  3. Combine the counted zeros and the strategically placed ones to form the longest possible subsequence.
  4. The number of zeros plus the number of ones we were able to include gives us the length of the longest subsequence.

Code Implementation

def longest_binary_subsequence(
    binary_string: str, maximum_value: int
) -> int:
    zero_count = 0
    one_count = 0
    current_value = 0

    # Count the zeros
    for bit in binary_string:
        if bit == '0':
            zero_count += 1

    # Include ones from right to left
    for i in range(len(binary_string) - 1, -1, -1):
        if binary_string[i] == '1':

            # Adding a '1' may exceed the limit
            if current_value + (1 << (len(binary_string) - 1 - i)) <= maximum_value:
                current_value += (1 << (len(binary_string) - 1 - i))
                one_count += 1

    # Return the length of the longest subsequence
    return zero_count + one_count

Big(O) Analysis

Time Complexity
O(n)Counting the zeros requires iterating through the entire input array once, which takes O(n) time, where n is the length of the input string. Determining how many ones can be included without exceeding the limit K also requires iterating through a portion of the input string from right to left, at most n times. Since these operations are performed sequentially, the overall time complexity is dominated by the linear iteration of the input string, thus the time complexity is O(n).
Space Complexity
O(1)The solution counts the number of zeros and then iterates to include ones, using a constant number of integer variables to keep track of the count of zeros and the current binary value calculated from the ones. No auxiliary data structures like arrays, lists, or hash maps are used to store intermediate results, regardless of the input size N (length of the input binary string). The space used by the algorithm therefore remains constant.

Edge Cases

CaseHow to Handle
Empty binary stringReturn 0 as there's no subsequence.
k is zero and the string contains only 1sReturn 0 as no subsequence is less than or equal to k.
k is negativeReturn 0 as binary subsequences are always positive.
String contains only zeros and k is greater than zeroReturn the length of the string, as any subsequence is valid.
String contains only ones and k is less than the smallest subsequence's value (1)Return 0 because no subsequence satisfies the condition.
Integer overflow when calculating the decimal value of a long subsequenceThe algorithm should efficiently count '0's and a limited number of '1's to prevent integer overflow when calculating subsequences.
k is very large (close to max int) and string has many 1s.Limit the number of ones considered from the right to the number of bits required to represent k.
String of all ones, k is oneReturn 1, representing a single '1' subsequence.