2311. Longest Binary Subsequence Less Than or Equal to K

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^9

Method One: Greedy

Idea and Algorithm

The problem asks us to find the longest subsequence of s such that the corresponding binary number is ≤ k. Our first instinct is to prefer 0s over 1s, because compared to 1, a 0 at any position contributes a weight of 0 to the binary number's value.

Can we include all 0s? Yes, we can, because choosing 0 is always better than choosing 1. Suppose we have already selected a subsequence and now want to add a 0 to it. The 0 itself doesn't contribute to the binary value, but it will double the contribution of any 1s in higher positions. Since adding a 0 increases the subsequence length by 1, we could instead remove the highest-positioned 1, keeping the total length unchanged while ensuring the binary value doesn't increase. Therefore, choosing 0 is always better than choosing 1.

After selecting all 0s, we try to add as many 1s as possible. We can start from the lowest positions and add 1s greedily, ensuring the binary value remains ≤ k. Due to the constraint on k, we can pre-calculate the maximum possible position for a 1, rather than computing the contribution of each 1 position every time.

Under these two conditions, we calculate all positions that can be included in the subsequence and return the result.

Code

Python3

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        sm = 0                          
        cnt = 0   
        bits = k.bit_length()              
        for i, ch in enumerate(s[::-1]): 
            if ch == '1':                  
                if i < bits and sm + (1 << i) <= k:                   
                    sm += 1 << i
                    cnt += 1
            else:
                cnt += 1
        return cnt

C++

class Solution {
public:
    int longestSubsequence(string s, int k) {
        int sm = 0;
        int cnt = 0;
        int bits = 32 - __builtin_clz(k);
        for (int i = 0; i < s.size(); ++i) {
            char ch = s[s.size() - 1 - i];
            if (ch == '1') {
                if (i < bits && sm + (1 << i) <= k) {
                    sm += 1 << i;
                    cnt++;
                }
            } else {
                cnt++;
            }
        }
        return cnt;
    }
};

Java

class Solution {
    public int longestSubsequence(String s, int k) {
        int sm = 0;
        int cnt = 0;
        int bits = (int)(Math.log(k) / Math.log(2)) + 1;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(s.length() - 1 - i);
            if (ch == '1') {
                if (i < bits && sm + (1 << i) <= k) {
                    sm += 1 << i;
                    cnt++;
                }
            } else {
                cnt++;
            }
        }
        return cnt;
    }
}

C#

public class Solution {
    public int LongestSubsequence(string s, int k) {
        int sm = 0;
        int cnt = 0;
        int bits = (int)(Math.Log(k, 2)) + 1;
        for (int i = 0; i < s.Length; i++) {
            char ch = s[s.Length - 1 - i];
            if (ch == '1') {
                if (i < bits && sm + (1 << i) <= k) {
                    sm += 1 << i;
                    cnt++;
                }
            } else {
                cnt++;
            }
        }
        return cnt;
    }
}

C

int longestSubsequence(char * s, int k){
    int sm = 0;
    int cnt = 0;
    int bits = (int)(log2(k)) + 1;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        char ch = s[len - 1 - i];
        if (ch == '1') {
            if (i < bits && sm + (1 << i) <= k) {
                sm += 1 << i;
                cnt++;
            }
        } else {
            cnt++;
        }
    }
    return cnt;
}

JavaScript

var longestSubsequence = function(s, k) {
    let sm = 0;
    let cnt = 0;
    let bits = Math.log2(k) + 1;
    for (let i = 0; i < s.length; i++) {
        const ch = s[s.length - 1 - i];
        if (ch === '1') {
            if (i < bits && sm + (1 << i) <= k) {
                sm += 1 << i;
                cnt++;
            }
        } else {
            cnt++;
        }
    }
    return cnt;
};

TypeScript

function longestSubsequence(s: string, k: number): number {
    let sm = 0;
    let cnt = 0;
    let bits = Math.log2(k) + 1;
    for (let i = 0; i < s.length; i++) {
        const ch = s[s.length - 1 - i];
        if (ch === '1') {
            if (i < bits && sm + (1 << i) <= k) {
                sm += 1 << i;
                cnt++;
            }
        } else {
            cnt++;
        }
    }
    return cnt;
};

Golang

func longestSubsequence(s string, k int) int {
    sm := 0
    cnt := 0
    bits := bits.Len(uint(k))
    for i := 0; i < len(s); i++ {
        ch := s[len(s) - 1 - i]
        if ch == '1' {
            if i < bits && sm + (1 << i) <= k {
                sm += 1 << i
                cnt++
            }
        } else {
            cnt++
        }
    }
    return cnt
}

Rust

impl Solution {
    pub fn longest_subsequence(s: String, k: i32) -> i32 {
        let mut sm = 0;
        let mut cnt = 0;
        let bits = (k as f64).log2() as usize + 1;
        for (i, ch) in s.chars().rev().enumerate() {
            if ch == '1' {
                if i < bits && sm + (1 << i) <= k {
                    sm += 1 << i;
                    cnt += 1;
                }
            } else {
                cnt += 1;
            }
        }
        cnt
    }
}

Complexity Analysis

• Time Complexity: $O(n)$, where $n$ is the length of string $s$.
• Space Complexity: $O(1)$.