Get started

Longest Binary Subsequence Less Than or Equal to K — Medium Problem & Solution

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.

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

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

  1. Count all the zeros — every one of them joins the subsequence.
  2. Sweep from the right, tracking the place value pow of the next position (1, 2, 4, …).
  3. Take a '1' whenever pow <= k and the running value plus pow stays at or below k.

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

  • pow doubles without a guard and overflows quickly — stop once it exceeds k.
  • Taking ones from the left picks the expensive ones first and under-counts.
  • Zeros are always included, even when k is 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 + 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue