LeetCode Daily Challenge-2311. Longest Binary Subsequence Less Than or Equal to K(Easy)

• LeetCode Link
• Topics: String, Dynamic Programming, Greedy
• Date: 26th June 2025

Problem Statement

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 have leading zeros.

Understanding the Problem

A subsequence is a sequence that can be derived from the original string by deleting some or no elements without changing the order of the remaining elements. For example, from "1001", we can form subsequences like "11", "01", "001", etc.

The key challenge is finding the longest possible subsequence where the resulting binary number doesn't exceed k.

The Greedy Strategy

The solution uses a clever greedy approach based on three critical insights:

1. All Zeros Are "Free"

Leading zeros don't affect the value of a binary number. This means we can always include all zeros from the original string in our subsequence without worrying about exceeding k.

2. Process Ones from Right to Left

For the '1' bits, we should be greedy and pick them from right to left (least significant bit first). This approach maximizes our chances of including more '1' bits while staying within the limit.

3. Bit Position Values

Each bit position has a specific value: the rightmost bit represents 2⁰ = 1, the next bit represents 2¹ = 2, then 2² = 4, and so on. By processing from right to left, we're essentially asking: "Can I afford to include this bit value?"

Code Walkthrough

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        zeros = s.count('0')  # All zeros can always be included

        # Special case: if k is 0, only zeros are allowed
        if k == 0:
            return zeros

        # Greedily include '1' bits from right to left
        current_value = 0
        ones_count = 0
        bit_value = 1  # Value of current bit position (2^0, 2^1, 2^2, ...)

        # Process string from right to left
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '1':
                # Can we include this '1' without exceeding k?
                if current_value + bit_value <= k:
                    current_value += bit_value
                    ones_count += 1

            # Move to next higher bit position
            bit_value *= 2

            # Optimization: if current bit value > k, no more '1's can fit
            if bit_value > k:
                break

        return zeros + ones_count

Step-by-Step Execution

Let's trace through an example: s = "1001010", k = 5

1. Count zeros: zeros = 3 (we can always include all zeros)
2. Special case check: k ≠ 0, so we continue

3. Process from right to left:

   • Position 6 (rightmost): s[6] = '0', bit_value = 1
   • Position 5: s[5] = '1', bit_value = 2
     • Can we add 2? current_value + 2 = 0 + 2 = 2 ≤ 5 ✓
     • current_value = 2, ones_count = 1
   • Position 4: s[4] = '0', bit_value = 4
   • Position 3: s[3] = '1', bit_value = 8
     • Can we add 8? current_value + 8 = 2 + 8 = 10 > 5 ✗
   • Position 2: s[2] = '0', bit_value = 16
     • bit_value = 16 > k = 5, so we break (optimization)

4. Final result: zeros + ones_count = 3 + 1 = 4

The optimal subsequence would be "0010" (all zeros plus the '1' at position 5), which represents binary 10 = decimal 2.

Time and Space Complexity

• Time Complexity: O(n) where n is the length of the string. We process each character at most once.
• Space Complexity: O(1) as we only use a constant amount of extra space.

Key Optimization

The line if bit_value > k: break is crucial for efficiency. Once the current bit position value exceeds k, no subsequent '1' bits can possibly fit within our limit, so we can terminate early.

Alternative Approaches Considered

You might think about using dynamic programming or exploring all possible subsequences, but the greedy approach is optimal here because:

1. Including zeros never hurts (they don't increase the value)
2. For ones, including lower-order bits first gives us the maximum flexibility for future decisions
3. The binary representation naturally lends itself to this greedy strategy

Edge Cases to Consider

• When k = 0: Only zeros can be included
• When the string contains only zeros: All can be included
• When the string contains only ones: Process greedily from right to left
• When k is very large: Most or all bits can likely be included

This solution elegantly combines mathematical insight with algorithmic efficiency, making it an excellent example of how understanding the problem domain (binary numbers) leads to an optimal greedy strategy.