Find the maximum-length subsequence of a binary string whose numeric value is at most k.
Problem
You are given a binary string s and an integer k.
A subsequence is formed by deleting zero or more characters from s without changing the order of the remaining characters.
Return the length of the longest subsequence of s whose binary value is less than or equal to k.
The chosen subsequence may contain leading zeroes, and its binary value is interpreted in the usual way.
Key idea
You do not need to form the lexicographically smallest subsequence. The goal is only to maximize length while keeping the value within the limit k.
Input Format
s: a binary string consisting of characters'0'and'1'k: a non-negative integer limit
Output Format
- Return a single integer: the maximum possible length of a subsequence of
swhose binary value is<= k.
Constraints
1 <= s.length <= $10^{5}$s[i]is either'0'or'1'0 <= k <= $10^{9}$
Example 1
Input
s = "1001010", k = 5
Output
5
Explanation
One optimal subsequence is "00010", which has binary value 2 and length 5.
Example 2
Input
s = "00101001", k = 1
Output
6
Explanation
Keep all zeroes and only one 1 that can fit within the limit. One valid subsequence is "000001", whose value is 1 and length is 6.
Show 1 more example
Example 3
Input
s = "1111", k = 0
Output
0
Explanation
No subsequence containing 1 is allowed, so the best answer is 0.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.