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:
0.
Example 1:
Input: s = "1001010", k = 5 Output: 5 Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal. Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively. The length of this subsequence is 5, so 5 is returned.
Example 2:
Input: s = "00101001", k = 1 Output: 6 Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal. The length of this subsequence is 6, so 6 is returned.
Constraints:
1 <= s.length <= 1000s[i] is either '0' or '1'.1 <= k <= 109Problem Overview: You receive a binary string s and an integer k. The task is to pick a subsequence of s that forms a binary number less than or equal to k, while maximizing the subsequence length. The subsequence must preserve order, but you can skip characters.
Approach 1: Dynamic Programming with Memoization (O(n * log k) time, O(n * log k) space)
This approach models the decision process for each index: include the current bit or skip it. The state typically tracks the current position and the value of the binary number formed so far. Because the value grows exponentially with appended bits, you cap the tracked value at k. Use memoization to avoid recomputing overlapping states. Each recursive step branches into two choices and stores the best result. The complexity depends on the maximum number of bits needed to represent k, which is roughly log₂(k). This method is useful when demonstrating classic dynamic programming thinking or when reasoning about subsequences systematically.
Approach 2: Greedy from Right to Left (O(n) time, O(1) space)
The optimal solution relies on a key observation about binary numbers. Bits on the right contribute less to the value than bits on the left. When building the subsequence, you want to include as many low-weight bits as possible. Start scanning from the rightmost character of the string. Keep track of the current value and the bit weight (1, 2, 4, 8...). If adding a '1' keeps the value ≤ k, include it and update the value. Always include '0' because it does not increase the number's value but increases subsequence length. Stop considering '1's once the bit weight exceeds k, since any further '1' would push the value beyond the limit. This greedy logic works because choosing smaller positional weights first maximizes the number of usable bits. The algorithm performs a single pass and uses constant extra memory, making it ideal for interview settings involving greedy algorithms.
Recommended for interviews: The greedy solution is what interviewers typically expect. It shows you understand how binary positional weights affect numeric value and how to exploit that structure for an O(n) pass. Discussing the dynamic programming formulation first can help demonstrate problem‑solving depth, but implementing the greedy approach shows stronger optimization skills.
In this approach, we will aim to maximize the count of '0's in the subsequence because they contribute a value of 0 to the binary number, ensuring it stays small. We then try to add as many '1's as we can while ensuring that the binary number formed remains less than or equal to k.
This implementation iterates from the least significant to the most significant bit of the string. It initially prioritizes adding '0's because they do not impact the current numerical value 'value'. For each '1' encountered, a check is performed to see if adding this '1', would result in a binary number less than or equal to k. If it does, the '1' is accepted, otherwise, it is skipped.
The time complexity is O(n), where n is the length of the binary string, since we iterate through the string once. The space complexity is O(1) since only a few variables are used.
This approach leverages dynamic programming to store intermediate results and build up to the final output. It is generally less efficient than the greedy approach but illustrates a bottom-up method of solving the problem.
This method maintains a dynamic programming table where dp[i] corresponds to the longest subsequence from the start collapsing to i. For each '0', it elongates the subsistence without consideration of numerical limits, checking each '1' iteratively against increasing binary weights and augmenting upon acceptance.
The time complexity leverage here is O(n^2) due to dual allocation iterations over i and n bits, with space complexity as O(n) for intermediate storages.
The longest binary subsequence must include all the 0s in the original string. On this basis, we traverse s from right to left. If we encounter a 1, we check if adding this 1 to the subsequence keeps the binary number v leq k.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
C#
Rust
| Approach | Complexity |
|---|---|
| Greedy Approach | The time complexity is O(n), where n is the length of the binary string, since we iterate through the string once. The space complexity is O(1) since only a few variables are used. |
| Dynamic Programming Approach (Less Optimal) | The time complexity leverage here is O(n^2) due to dual allocation iterations over i and n bits, with space complexity as O(n) for intermediate storages. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Memoization | O(n * log k) | O(n * log k) | When exploring all subsequence decisions or explaining a systematic DP formulation |
| Greedy Right-to-Left Bit Selection | O(n) | O(1) | Best choice for interviews and large inputs where a single linear pass is required |
Longest Binary Subsequence Less Than or Equal to K | 2 Ways | Leetcode 2311 | codestorywithMIK • codestorywithMIK • 9,438 views views
Watch 9 more video solutions →Practice Longest Binary Subsequence Less Than or Equal to K with our built-in code editor and test cases.
Practice on FleetCode