难度: Medium
给你一个二进制字符串 s 和一个正整数 k 。
请你返回 s 的 最长 子序列，且该子序列对应的 二进制 数字小于等于 k 。
注意：
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 <= 1000s[i] 要么是 '0' ，要么是 '1' 。1 <= k <= 109运行时间: 22 ms
内存: 16.1 MB
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')
# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/longest-binary-subsequence-less-than-or-equal-to-k/solutions/1611120/fen-lei-tao-lun-tan-xin-by-endlesscheng-vnlx/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这个题解利用了二进制数的性质和长度限制的思想。首先，计算给定整数 k 的二进制表示的长度 m。理论上，任何长度超过 m 的二进制序列都会大于 k，因此不需要考虑 s 中长度超过 m 的部分。接着，检查 s 中最后 m 位形成的二进制数是否小于等于 k；如果是，这 m 位都可用；如果不是，则只能使用 m-1 位。最后，除了最后 m 位的其他部分，可以贪心地加入所有 '0'（因为 '0' 不增加数值但可以增加长度），从而得到最长的符合条件的子序列。这种方法直接通过数学计算和贪心策略找到结果，避免了复杂的搜索或动态规划算法。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def longestSubsequence(self, s: str, k: int) -> int:
n, m = len(s), k.bit_length() # n 是字符串长度, m 是 k 的二进制位数
if n < m: return n # 如果字符串长度小于 k 的二进制长度，直接返回 n
# 检查 s 的最后 m 位是否小于等于 k
ans = m if int(s[-m:], 2) <= k else m - 1
return ans + s[:-m].count('0') # 返回 ans 加上除了最后 m 位外 '0' 的数量
计算整数 k 的二进制表示的长度 m 是为了确定二进制序列的长度上限。因为任何长度超过 m 的二进制序列的数值都将大于 k，所以知道 m 可以帮助我们有效地限制考虑的子序列的长度，从而简化问题。此外，这也是一种确保我们不会处理不必要的数据量并优化性能的方法。
这种处理方式是基于贪心策略，并不会遗漏情况。因为如果最后 m 位的数值已经超过了 k，那么任何包含这 m 位的子序列都将不符合要求。因此，在这种情况下使用 m-1 位是安全的，确保子序列的数值不会超过 k。此外，由于我们已经知道最后 m-1 位肯定小于最后 m 位，所以这种方法是有效且完备的。
在这个问题中，'0' 不会增加二进制数的数值，因此可以安全地加入任何额外的 '0' 来增加序列的长度而不影响其值。这种贪心策略适用于所有情况，因为 '0' 的添加总是安全的，不会使序列的值超过 k。因此，没有特殊情况使这种方法不适用。
避免使用复杂的搜索或动态规划算法的主要优势在于效率和简洁性。通过直接计算和使用贪心策略，算法的时间复杂度和空间复杂度都得以优化，使得解决方案更快且消耗更少资源。此外，这种方法提供了更直观的解决方案，便于理解和实现。