Skip to main content
Talentd

Longest Binary Subsequence Less Than or Equal to K - Solution & Explanation

MediumStringDynamic ProgrammingGreedyMemoization19 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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 = 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 <= 1000
  • s[i] is either '0' or '1'.
  • 1 <= k <= 109

Approach Overview

Problem 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.

Approach 1: Greedy Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach (Less Optimal)

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Greedy

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).

Code

PythonJavaC++GoTypeScriptJavaScriptC#Rust

Python

Java

C++

Go

TypeScript

JavaScript

C#

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with MemoizationO(n * log k)O(n * log k)When exploring all subsequence decisions or explaining a systematic DP formulation
Greedy Right-to-Left Bit SelectionO(n)O(1)Best choice for interviews and large inputs where a single linear pass is required

Video Solution

Longest Binary Subsequence Less Than or Equal to K | 2 Ways | Leetcode 2311 | codestorywithMIK • codestorywithMIK • 9,674 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Binary Subsequence Less Than or Equal to K easy or hard?
This problem is generally classified as Medium difficulty. The challenge lies in recognizing the greedy property of binary positional weights. Once that insight is clear, the implementation becomes straightforward and runs in linear time.
Longest Binary Subsequence Less Than or Equal to K Python/Java solution
Most implementations use the greedy method. Iterate from the end of the string, track the current value and power-of-two weight, and count valid bits. The same logic translates directly to Python, Java, C++, JavaScript, and other languages with identical O(n) time complexity.
How to solve Longest Binary Subsequence Less Than or Equal to K in O(n)?
Scan the string from right to left while maintaining the current binary value and bit weight. Always include '0' because it increases length without increasing value. For '1', include it only if the resulting value does not exceed k. Stop considering further '1's once the bit weight becomes larger than k.
What is the best approach for Longest Binary Subsequence Less Than or Equal to K?
The greedy right-to-left approach is the most efficient. Traverse the binary string from the end, always include '0', and include '1' only if its positional value keeps the number ≤ k. This works because rightmost bits have the smallest contribution to the final value. The algorithm runs in O(n) time with O(1) extra space.
Is Longest Binary Subsequence Less Than or Equal to K asked at Google/Amazon/Meta?
Problems involving greedy reasoning with binary representation frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. Variants of subsequence selection and binary value constraints are common in medium-level interview rounds.
What data structure is used in Longest Binary Subsequence Less Than or Equal to K?
The greedy solution uses simple variables to track the current value and bit weight while iterating through the string. No complex data structures are required. The alternative dynamic programming approach may use recursion with memoization or a DP table to store intermediate results.
What is the time complexity of Longest Binary Subsequence Less Than or Equal to K?
The optimal greedy solution runs in O(n) time where n is the length of the binary string. It performs a single pass while maintaining the current value and bit weight. A dynamic programming alternative may take O(n * log k) time due to tracking possible values up to the bit length of k.

Ready to solve this problem?

Practice Longest Binary Subsequence Less Than or Equal to K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Binary String After Change