目标
给你一个二进制字符串 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。
可以计算出 k 的二进制表示 target，长度 l 最大为 30。问题的关键是能否找到长度为 l 的子序列，使得它小于等于 target，显然长度小于 l 的二进制数字必定小于等于 target。但是可以包含前导零，那么只要是 0 就可以加到左边。
贪心策略：判断长为 l 的后缀是否小于等于 k，如果是，则结果加上 l，否则加上 l - 1，然后再累加上 0 ~ n - l - 1 中 0 的个数即可。
代码
/**
* @date 2025-06-26 8:47
*/
public class LongestSubsequence2311 {
public int longestSubsequence(String s, int k) {
int res = 0;
s = "0" + s;
int n = s.length();
long base = 2;
long v = s.charAt(n - 1) - '0';
for (int i = n - 1; i > 0; i--) {
if (v <= k) {
res++;
v += base * (s.charAt(i - 1) - '0');
if (base <= k) {
base *= 2;
}
} else if (s.charAt(i) == '0') {
res++;
}
}
return res;
}
}
性能
