Longest Binary Subsequence Less Than or Equal to K

medium greedy bit manipulation binary string

Problem

Given a binary string s and a positive integer k, return the length of the longest subsequence of s whose binary value is less than or equal to k. The subsequence may contain leading zeroes, and the empty string counts as 0.

Inputs = "1001010", k = 5

Output5

"00010" equals 2 in decimal (≤ 5) and has length 5; no valid subsequence is longer.

Inputs = "00101001", k = 1

Output6

"000001" equals 1 in decimal (≤ 1) and has length 6.

s (binary string)

k (positive integer)

def longest_subsequence(s, k):
    val = 0
    cnt = 0
    for i in range(len(s) - 1, -1, -1):
        if s[i] == '0':
            cnt += 1
        elif cnt < 30 and val + (1 << cnt) <= k:
            val += (1 << cnt)
            cnt += 1
    return cnt

function longestSubsequence(s, k) {
  let val = 0, cnt = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === '0') {
      cnt++;
    } else if (cnt < 30 && val + (1 << cnt) <= k) {
      val += (1 << cnt);
      cnt++;
    }
  }
  return cnt;
}

int longestSubsequence(String s, int k) {
    long val = 0;
    int cnt = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '0') {
            cnt++;
        } else if (cnt < 30 && val + (1L << cnt) <= k) {
            val += (1L << cnt);
            cnt++;
        }
    }
    return cnt;
}

int longestSubsequence(string s, int k) {
    long long val = 0;
    int cnt = 0;
    for (int i = (int)s.size() - 1; i >= 0; i--) {
        if (s[i] == '0') {
            cnt++;
        } else if (cnt < 30 && val + (1LL << cnt) <= k) {
            val += (1LL << cnt);
            cnt++;
        }
    }
    return cnt;
}

Explanation

To make a subsequence as long as possible while keeping its binary value ≤ k, two facts guide a greedy scan from right to left.

First, every 0 is essentially free: appending a zero on the high end (or any position) never raises the numeric value, so we always take it. Each character we keep also shifts later kept characters into a higher bit position, so we track the count of kept characters in cnt — that count is exactly the power of two a future 1 would carry.

Second, a 1 at the current scan position would contribute 1 << cnt to the value (where cnt is how many characters we have already kept to its right). We take that 1 only if the running value val stays within k after adding it: val + (1 << cnt) ≤ k. The cnt < 30 guard simply avoids overflow once the weight already exceeds any reachable k.

Because we always grab cheaper low-order ones first (right to left) and never reject a zero, the kept set is simultaneously the longest and the smallest-valued, so it is optimal.

Example: s = "1001010", k = 5. Scanning right to left we take the trailing 0, then the 1 (weight 2, value 2 ≤ 5), more zeros, but reject the higher 1s whose weight (8, then 32) would exceed 5. Five characters are kept, so the answer is 5.

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