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

Longest Binary Subsequence Less Than or Equal to K

Difficulty: Medium

Problem Description

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.

Key Insights

  • A subsequence can include leading zeros.
  • The empty string is treated as equal to 0.
  • The solution needs to derive a valid binary number from the string s such that its decimal value does not exceed k.
  • The approach involves checking how many zeros can be included and how many ones can be included without exceeding the given value of k.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can iterate through the binary string s and count the number of 0s and 1s. The binary number represented by the longest subsequence can have all the 0s and a limited number of 1s based on the value of k. We need to check if including a 1 keeps the binary number less than or equal to k. This can be done by maintaining a count of the decimal value of the formed binary number and comparing it with k.

Code Solutions

def longestSubsequence(s: str, k: int) -> int:
    count_0 = s.count('0')  # Count of zeros in the string
    count_1 = 0  # Count of ones we can include
    current_value = 0  # Current value of the binary number

    # Iterate through the string to count the usable ones
    for char in s:
        if char == '1':
            # Check if adding this '1' keeps us <= k
            if current_value + (1 << count_1) <= k:
                count_1 += 1  # We can include this '1'
            else:
                break  # No need to check further as higher ones will also exceed

    # The total length of the longest subsequence is count of 0s + count of usable 1s
    return count_0 + count_1
← Back to All Questions