Longest binary subsequence less than or equal to k

String Dynamic Programming Greedy Memoization

52.8% acceptance

Feb 25, 2026

1144

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn longest_subsequence(s: String, k: i32) -> i32 {
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();
    let zeros = chars.iter().filter(|&&c| c == '0').count() as i32;
    let mut zeros_seen = 0i32;
    let mut ones_included = 0i32;
    let mut val: i64 = 0;
    let k_val = k as i64;
    for i in (0..n).rev() {
      if chars[i] == '0' {
        zeros_seen += 1;
      } else {
        let bit_pos = zeros_seen + ones_included;
        if bit_pos < 31 {
          let add = 1i64 << bit_pos;
          if val + add <= k_val {
            val += add;
            ones_included += 1;
          }
        }
      }
    }
    zeros + ones_included
  }
}