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 = 5Output
5The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", whose decimal value is 2, and its length is 5.
Example 2
Input
s = "00101001", k = 1Output
6"000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, and its length is 6.
Constraints
- 1 <= s.length <= 1000
- s[i] is either '0' or '1'.
- 1 <= k <= 10^9