Longest Binary Subsequence Less Than or Equal to K Solution
Longest Binary Subsequence Less Than or Equal to K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Binary Subsequence Less Than or Equal to K is a medium coding problem on strings, dynamic programming and greedy, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming, Greedy, Memoization
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return the length of the longest subsequence of the binary string s whose value, read as a binary number, is at most k. Leading zeros are allowed.
Example 1
Input: s = "1001010", k = 5
Output: 5
Explanation: Taking "00010" gives the value 2.
Example 2
Input: s = "00101001", k = 1
Output: 6
Explanation: Taking "000001" gives the value 1.
Example 3
Input: s = "1", k = 0
Output: 0
Constraints
1 <= s.length <= 1000s[i] is '0' or '1'1 <= k <= 1000000000
Hints for Longest Binary Subsequence Less Than or Equal to K
Hint 1
Every
'0'can be taken for free — leading zeros do not change the value.Hint 2
So the only question is how many
'1's to keep, and which.Hint 3
Ones nearer the right carry smaller place values, so take them first while the total stays within
k.
How to solve Longest Binary Subsequence Less Than or Equal to K
Zeros are always free, so the answer is (number of zeros) + (maximum number of ones affordable). Among the ones, the cheapest to keep are the rightmost, because their place value in the resulting subsequence is smallest.
Approach
- Count all the zeros — every one of them joins the subsequence.
- Sweep from the right, tracking the place value
powof the next position (1, 2, 4, …). - Take a
'1'wheneverpow <= kand the running value pluspowstays at or belowk.
Why it works
Dropping a '0' never reduces the value but always shortens the subsequence, so keeping all of them is free and optimal. For the ones, the j-th kept one from the right contributes at least 2^j, so keeping the rightmost ones minimises the total for any fixed count — making the greedy count maximal. Once pow exceeds k, no further one can be afforded, so the sweep can stop growing it.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
powdoubles without a guard and overflows quickly — stop once it exceedsk.- Taking ones from the left picks the expensive ones first and under-counts.
- Zeros are always included, even when
kis tiny.
Reference solution
Python
def longestSubsequence(s: str, k: int) -> int:
zeros = s.count("0")
val = ones = 0
pow2 = 1
for ch in reversed(s):
if ch == "1" and pow2 <= k and val + pow2 <= k:
val += pow2
ones += 1
if pow2 <= k:
pow2 *= 2
return zeros + onesJava
public static int longestSubsequence(String s, int k) {
int n = s.length(), zeros = 0;
for (int i = 0; i < n; i++) if (s.charAt(i) == '0') zeros++;
long val = 0, pow = 1;
int ones = 0;
for (int i = n - 1; i >= 0; i--) {
if (s.charAt(i) == '1' && pow <= k && val + pow <= k) {
val += pow;
ones++;
}
if (pow <= k) pow *= 2;
}
return zeros + ones;
}C++
int longestSubsequence(string s, int k) {
int n = (int) s.size(), zeros = 0;
for (char ch : s) if (ch == '0') zeros++;
long long val = 0, pw = 1;
int ones = 0;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '1' && pw <= k && val + pw <= k) {
val += pw;
ones++;
}
if (pw <= k) pw *= 2;
}
return zeros + ones;
}JavaScript
var longestSubsequence = function(s, k) {
var n = s.length, zeros = 0, i;
for (i = 0; i < n; i++) if (s.charAt(i) === "0") zeros++;
var val = 0, ones = 0, pow = 1;
for (i = n - 1; i >= 0; i--) {
if (s.charAt(i) === "1" && pow <= k && val + pow <= k) { val += pow; ones++; }
if (pow <= k) pow *= 2;
}
return zeros + ones;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming