{x}
blog image

Longest Binary Subsequence Less Than or Equal to K

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 subsequence can contain leading zeroes.
  • The empty string is considered to be equal to 0.
  • 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.

 

Example 1:

Input: s = "1001010", k = 5
Output: 5
Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal.
Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively.
The length of this subsequence is 5, so 5 is returned.

Example 2:

Input: s = "00101001", k = 1
Output: 6
Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
The length of this subsequence is 6, so 6 is returned.

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'.
  • 1 <= k <= 109

Solution Explanation

This problem asks to find the length of the longest subsequence of a binary string s such that the resulting binary number is less than or equal to k. The solution uses a greedy approach, iterating through the string from right to left.

Approach:

The algorithm cleverly leverages bit manipulation to efficiently check if adding a '1' to the current subsequence will exceed k. It processes the binary string from right to left:

  1. Initialization: ans keeps track of the length of the subsequence, and v stores the current decimal value of the subsequence. Both are initialized to 0.

  2. Iteration: The code iterates through s from the last character to the first.

  3. '0' Handling: If the current character is '0', it's always beneficial to add it to the subsequence, increasing ans.

  4. '1' Handling: If the character is '1', the algorithm checks if adding it to the subsequence will still result in a value less than or equal to k. This is done using bitwise operations:

    • 1 << ans: This left-shifts 1 by ans bits, effectively creating a binary number with a '1' at the ans-th position (from the right) and zeros elsewhere.
    • v | (1 << ans): This performs a bitwise OR operation between the current value (v) and the newly created number. This simulates adding a '1' at the ans-th position.
    • (v | (1 << ans)) <= k: This condition checks if adding the '1' keeps the value less than or equal to k.

    If the condition is true, the '1' is added, v is updated, and ans is incremented.

  5. Result: Finally, ans (the length of the subsequence) is returned.

The time complexity is O(n) because the code iterates through the string once. The space complexity is O(1) because only a few integer variables are used, regardless of the input size.

Code Explanation (Python)

The Python code efficiently implements this approach using bit manipulation:

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        ans = v = 0  # Initialize ans (subsequence length) and v (decimal value)
        for c in s[::-1]:  # Iterate from right to left
            if c == "0":
                ans += 1  # Add '0' to subsequence
            elif ans < 30 and (v | 1 << ans) <= k:  # Check if adding '1' is valid
                v |= 1 << ans  # Add '1' to subsequence (bitwise OR)
                ans += 1  # Increment subsequence length
        return ans  # Return length of longest subsequence

The ans < 30 condition is a safeguard; it prevents potential integer overflow issues if ans gets too large, which is unlikely with the constraints given (s.length <= 1000).

The other languages provide the same logic with slight syntactic differences. The core idea remains consistent across all implementations.