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.

Description Hints 2 Solution Video 22:54

2311. Longest Binary Subsequence Less Than or Equal to K

Medium52.8% acceptance3 companies

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 <= 10⁹

Asked at 3 companies

Google Bloomberg Amazon

Topics

Hints open one at a time

Hint 1

Choosing a subsequence from the string is equivalent to deleting all the other digits.

Hint 2

If you were to remove a digit, which one should you remove to reduce the value of the string?

22:54

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution