2311. 小于等于 K 的最长二进制子序列

给你一个二进制字符串 s 和一个正整数 k。

请你返回 s 的 最长 子序列的长度，且该子序列对应的二进制数字 小于等于 k。

注意：

• 子序列可以有 前导 0。
• 空字符串视为 0。
• 子序列是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。

示例 1

输入：s = "1001010", k = 5

输出：5

解释： s 中小于等于 5 的最长子序列是 "00010"，对应的十进制数字是 2。 注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5。 最长子序列的长度为 5，所以返回 5。

示例 2

输入：s = "00101001", k = 1

输出：6

解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1。 最长子序列的长度为 6，所以返回 6。

提示

• 1 <= s.length <= 1000
• s[i] 要么是 '0'，要么是 '1'。
• 1 <= k <= 10^9

方法一：贪心

思路与算法

题目要求选出 s 的最长子序列，并且这个子序列的二进制数字要 ≤ k。第一反应是要多选 0，因为和 1 相比，0 这一位对二进制数的值带来的权重为 0。

那么，把所有的 0 都加入可以吗？是可以的，因为选 0 一定比选 1 好。假如已经选出了一个子序列，现在要在其中加入一个 0。0 本身不会对二进制的值产生贡献，但它会使得比它更高位的 1 产生的贡献加倍。因为加入一个 0 使得子序列的长度变大了 1，我们不妨移除最高位的 1，这样总长度不变，但是二进制的值一定不会变大。因此，选 0 一定比选 1 好。

在选全部 0 的情况下，我们再尽可能地往里面加 1。这时，我们可以从低位开始，尽可能地加，并且保证二进制的值始终 ≤ k。因为 k 值的限制，我们可以提前算出 1 可能的最高位，而不用每次都去计算这一位的 1 产生的贡献。

在这两个条件下，我们算出所有可以加入子序列的位，然后返回结果。

代码

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
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。
• 空间复杂度：$O(1)$。