What is the key technique used in solving 'Longest Binary Subsequence Less Than or Equal to K'?

The key technique is state transition dynamic programming, which efficiently keeps track of the subsequences formed by the binary string.

How do greedy methods apply to this problem?

Greedy methods are used to select digits from the string that form the longest subsequence while maintaining the condition that the number formed is less than or equal to k.

Why is dynamic programming crucial for this problem?

Dynamic programming is essential for tracking the possible subsequences and ensuring that the binary number formed remains less than or equal to k.

How can I avoid common mistakes in this problem?

Ensure that you correctly manage the state transitions and use a greedy approach to select the most optimal subsequences.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the binary string, as you only need to iterate through the string once.

#2311

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个二进制字符串 s 和一个正整数 k 。请你返回 s 的最长子序列的长度，且该子序列对应的二进制数字小于等于 k 。注意：子序列可以有前导 0 。空字符串视为 0 。子序列是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。示例 1：输入： s =…

字符串动态规划贪心记忆化

题目描述

给你一个二进制字符串 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⁹

lightbulb

解题思路

方法一：贪心

最长二进制子序列必然包含原字符串中所有的 $0$ ，在此基础上，我们从右到左遍历 $s$ ，若遇到 $1$ ，判断子序列能否添加 $1$ ，使得子序列对应的二进制数字 $v \leq k$ 。

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

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        ans = v = 0
        for c in s[::-1]:
            if c == "0":
                ans += 1
            elif ans < 30 and (v | 1 << ans) <= k:
                v |= 1 << ans
                ans += 1
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Ability to apply dynamic programming to subsequence problems.
question_mark
Understanding of greedy methods for optimal subsequence selection.
question_mark
Skill in managing state transitions in an efficient manner.

warning

常见陷阱

外企场景

error
Failing to correctly manage the state transitions between valid subsequences.
error
Not considering the greedy selection of digits, leading to an incorrect subsequence.
error
Incorrect handling of subsequences that exceed the constraint k.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Problem variation with multiple constraints on k.
arrow_right_alt
Optimization when k is much larger or smaller than the length of the string.
arrow_right_alt
Modification where you can remove some digits, but not all, to form valid subsequences.

help

常见问题

外企场景

继续练习

#2472 不重叠回文子字符串的最大数目 #2522 将字符串分割成值不超过 K 的子字符串 #2086 喂食仓鼠的最小食物桶数