Problem Description

You have a binary string s (containing only '0's and '1's) and a positive integer k. Your task is to find the longest subsequence of s that, when interpreted as a binary number, has a value less than or equal to k.

A subsequence means you can pick characters from the original string while maintaining their relative order, but you don't have to pick consecutive characters. For example, if s = "1010", then "11", "00", "110", and "1010" are all valid subsequences.

Key points to remember:

• The subsequence can have leading zeros (e.g., "001" is valid and equals 1 in decimal)
• An empty subsequence is treated as having a value of 0
• You want to maximize the length of the subsequence, not its value

For example, if s = "1001010" and k = 5 (which is 101 in binary), you need to find the longest subsequence from "1001010" that represents a binary number ≤ 5. One possible answer could be the subsequence "00010" (length 5), which equals 2 in decimal.

The solution uses a greedy approach: it includes all '0's since they don't increase the value when added to the left side of a binary number. For '1's, it traverses from right to left and only includes a '1' if adding it at the current position keeps the total value ≤ k. The check ans < 30 prevents overflow since we're working with bit positions.

Intuition

To maximize the length of our subsequence, we should think about which bits contribute to the value and which don't. The key insight is that 0 bits are "free" - we can include all of them without increasing the binary value. So any optimal solution must include all 0s from the original string.

Now for the 1 bits, we need to be selective. Consider how binary numbers work: a 1 at position i (counting from the right, starting at 0) contributes 2^i to the total value. The leftmost bits have the highest contribution to the value.

This suggests a greedy strategy: process the string from right to left. Why? Because the rightmost 1s contribute less to the final value (2^0 = 1, 2^1 = 2, etc.) compared to leftmost 1s. By going right to left, we can greedily include 1s that have smaller contributions first.

Here's the clever part: as we traverse from right to left, we maintain a counter ans that represents both the length of our current subsequence AND the position where the next 1 would be placed if we include it. When we encounter a 1, we check if placing it at position ans (which would contribute 2^ans to our value) keeps us under k. If yes, we include it by setting that bit in our value v using v |= 1 << ans.

The condition ans < 30 is a practical safeguard - since we're dealing with typical integer constraints, we don't need to consider positions beyond 30 (as 2^30 is already over a billion).

This approach guarantees we get the maximum length because we're including all possible 0s and as many 1s as we can fit while staying under the limit k.

Learn more about Greedy, Memoization and Dynamic Programming patterns.

Solution Approach

The implementation follows a greedy approach by traversing the string from right to left. Here's how the algorithm works:

1. Initialize variables:

   • ans = 0: tracks the length of our subsequence and also represents the bit position for the next 1
   • v = 0: stores the actual binary value of our current subsequence

2. Traverse the string in reverse (s[::-1]):

   • When we encounter a '0':
     • Simply increment ans += 1 because zeros don't increase the binary value
     • We can include all zeros without any constraint
   • When we encounter a '1':
     • First check if ans < 30 to prevent overflow (since 2^30 is already very large)
     • Then check if adding this 1 at position ans keeps our value ≤ k
     • The check (v | 1 << ans) <= k tests what the new value would be if we set the bit at position ans
     • If both conditions pass, we:
       • Update our value: v |= 1 << ans (sets the bit at position ans)
       • Increment the length: ans += 1

3. Return the final length ans

The bit manipulation 1 << ans creates a number with only the bit at position ans set to 1. The OR operation v | (1 << ans) adds this bit to our current value.

Example walkthrough with s = "1001010" and k = 5:

• Reverse string: "0101001"
• Position 0: '0' → include it, ans = 1
• Position 1: '1' → check (0 | 1 << 1) = 2 <= 5 ✓, include it, v = 2, ans = 2
• Position 2: '0' → include it, ans = 3
• Position 3: '1' → check (2 | 1 << 3) = 10 > 5 ✗, skip it
• Position 4: '0' → include it, ans = 4
• Position 5: '0' → include it, ans = 5
• Position 6: '1' → check (2 | 1 << 5) = 34 > 5 ✗, skip it
• Result: length = 5

This greedy strategy ensures maximum length by including all zeros and as many ones as possible while respecting the constraint.

Example Walkthrough

Let's walk through a simple example with s = "10101" and k = 3 (which is 11 in binary).

Step 1: Reverse the string

• Original: "10101"
• Reversed: "10101" (happens to be palindromic)

Step 2: Process each character from the reversed string

Initialize: ans = 0, v = 0

• Index 0, char = '1':

  • Check: ans < 30? Yes (0 < 30)
  • Check: (0 | 1 << 0) = 1 <= 3? Yes
  • Include this '1': v = 0 | (1 << 0) = 1, ans = 1
  • Current subsequence represents: "1" = 1

• Index 1, char = '0':

  • It's a '0', always include: ans = 2
  • Current subsequence represents: "01" = 1

• Index 2, char = '1':

  • Check: ans < 30? Yes (2 < 30)
  • Check: (1 | 1 << 2) = 1 | 4 = 5 <= 3? No (5 > 3)
  • Skip this '1'
  • Current subsequence still: "01" = 1

• Index 3, char = '0':

  • It's a '0', always include: ans = 3
  • Current subsequence represents: "001" = 1

• Index 4, char = '1':

  • Check: ans < 30? Yes (3 < 30)
  • Check: (1 | 1 << 3) = 1 | 8 = 9 <= 3? No (9 > 3)
  • Skip this '1'
  • Final subsequence: "001" = 1

Result: Maximum length = 3

The subsequence we built is "001" (reading from the original string: we took positions 2, 3, and 4). This has value 1, which is ≤ 3, and has the maximum possible length of 3 characters.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through the string once in reverse order using s[::-1], performing constant-time operations for each character (bit manipulation operations like |, <<, and comparisons are O(1)).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space with variables ans, v, and c, regardless of the input size. Even though s[::-1] creates a reversed copy of the string, this is part of the input processing rather than auxiliary space used by the algorithm itself. The bit operations and integer storage do not scale with input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Position Calculation

A common mistake is misunderstanding how the bit position relates to the subsequence length. When traversing from right to left, subsequence_length represents both the current length AND the bit position for the next '1' we might add.

Wrong approach:

# Incorrectly using separate variables or wrong position calculation
bit_position = 0
for char in s[::-1]:
    if char == "1":
        if (current_value | (1 << bit_position)) <= k:  # Wrong position!
            current_value |= (1 << bit_position)
    bit_position += 1  # Incrementing regardless of inclusion

Correct approach: The subsequence_length variable serves dual purpose - it tracks how many characters we've included AND determines the bit position for the next '1'.

2. Forgetting the Overflow Check

Without checking subsequence_length < 30, the bit shift operation 1 << subsequence_length can cause integer overflow or unexpected behavior when the position gets large.

Wrong approach:

elif char == "1" and (current_value | (1 << subsequence_length)) <= k:
    # Missing overflow check - can cause issues with large strings

Correct approach: Always include the overflow check:

elif subsequence_length < 30 and (current_value | (1 << subsequence_length)) <= k:

3. Processing String in Wrong Direction

Processing the string from left to right (most significant bit first) makes it much harder to track the binary value correctly.

Wrong approach:

for char in s:  # Processing left to right
    # Complex logic needed to track positions and values

Correct approach: Process from right to left using s[::-1] to handle least significant bits first, making the bit position calculation straightforward.

4. Incorrectly Handling the Value Update

Using addition instead of bitwise OR can lead to incorrect results if you accidentally add the same bit position multiple times.

Wrong approach:

current_value += (1 << subsequence_length)  # Using addition

Correct approach:

current_value |= (1 << subsequence_length)  # Using bitwise OR

5. Not Including All Zeros

Some might try to optimize by limiting zeros, but the key insight is that ALL zeros should be included since they don't increase the binary value when added to the left.

Wrong approach:

if char == "0" and some_condition:  # Unnecessarily limiting zeros
    subsequence_length += 1

Correct approach:

if char == "0":
    subsequence_length += 1  # Always include zeros