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 <= 109

本题 视频讲解 已出炉，欢迎点赞三连~

---

提示 1

子序列的长度至少可以是多少？

提示 2

前导零不会改变二进制数的大小，因此要尽可能地往子序列前面添加前导零。

提示 3

我们应该在 s 中的一个靠后的位置找值不超过 k 的子序列，越靠后越好，因为这样前面能添加的前导零也就越多。

提示 4

找 s 中值不超过 k 的最长后缀，此时我们无法往这个后缀前面添加 1（否则值会超过 k），那么我们只能往这个后缀前面添加前导零。

提示 5

设 s 的长度为 n，k 的二进制长度为 m。

分类讨论：

• 如果 n<m，由于 k 最高位为 1，整个 s 对应的数字必然小于 k，此时返回 n；
• 如果 s 长为 m 的后缀 suf 对应的值不超过 k，那么我们可以从 s 的其余部分找尽可能多的 0，拼在 suf 前面；
• 如果 s 长为 m 的后缀对应的值超过 k，那么我们可以取 s 长为 m-1 的后缀 suf，这样对应的值小于 k，然后同上，从其余部分找尽可能多的 0，拼在 suf 前面。

复杂度分析

• 时间复杂度：O(n)，其中 n 为 s 的长度。这里是严格意义上的一次遍历，s 的每个字母都会被遍历恰好一次。
• 空间复杂度：O(1)，仅用到若干变量。（忽略子串的空间开销）

[sol1-Python3]

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        n, m = len(s), k.bit_length()
        if n < m: return n
        ans = m if int(s[-m:], 2) <= k else m - 1
        return ans + s[:-m].count('0')

[sol1-Java]

class Solution {
    public int longestSubsequence(String s, int k) {
        int n = s.length(), m = 32 - Integer.numberOfLeadingZeros(k);
        if (n < m) return n;
        var ans = Integer.parseInt(s.substring(n - m), 2) <= k ? m : m - 1;
        return ans + (int) s.substring(0, n - m).chars().filter(c -> c == '0').count();
    }
}

[sol1-C++]

class Solution {
public:
    int longestSubsequence(string s, int k) {
        int n = s.length(), m = 32 - __builtin_clz(k);
        if (n < m) return n;
        int ans = stoi(s.substr(n - m), nullptr, 2) <= k ? m : m - 1;
        return ans + count(s.begin(), s.end() - m, '0');
    }
};

[sol1-Go]

func longestSubsequence(s string, k int) int {
	n, m := len(s), bits.Len(uint(k))
	if n < m {
		return n
	}
	ans := m
	if v, _ := strconv.ParseInt(s[n-m:], 2, 0); int(v) > k {
		ans--
	}
	return ans + strings.Count(s[:n-m], "0")
}

变形题

把题目中的子序列改成子串要怎么做？