#2311

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Binary Subsequence Less Than or Equal to K

Find the longest subsequence in a binary string that forms a number less than or equal to a given integer k.

string dynamic programming greedy memoization

Problem Statement

You are given a binary string s and a positive integer k. Your task is to return the length of the longest subsequence of s that forms a binary number less than or equal to k.

A subsequence of a string is formed by deleting some (or no) characters without changing the order of the remaining characters. You must ensure that the binary number formed by the subsequence is less than or equal to k when converted to decimal.

Examples

Example 1

Input: s = "1001010", k = 5

Output: 5

The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal. Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively. The length of this subsequence is 5, so 5 is returned.

Example 2

Input: s = "00101001", k = 1

Output: 6

"000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal. The length of this subsequence is 6, so 6 is returned.

Constraints

1 <= s.length <= 1000
s[i] is either '0' or '1'.
1 <= k <= 109

Solution Approach

State Transition Dynamic Programming

You can approach the problem using dynamic programming to keep track of possible subsequences. The idea is to iterate over the string while keeping track of the current number formed by the subsequence and ensuring it remains less than or equal to k. By selecting digits and transitioning between states efficiently, the solution can be computed in linear time.

Greedy Selection with Dynamic Programming

A greedy approach can help in selecting the most optimal subsequence. By greedily considering the digits from left to right and updating the current state of the binary number, you can choose digits that maximize the subsequence length while maintaining the constraint of being less than or equal to k.

Efficient State Transition

Efficient state transition can be achieved by iterating through the string and updating the state at each step based on whether the current subsequence remains valid. The state transition approach ensures that you are always working with valid subsequences and only consider options that are possible under the constraint.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because you only need to iterate through the string once, processing each character in constant time. The space complexity is O(1) since you are only storing a few variables for the current state of the subsequence.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Greedy

The longest binary subsequence must include all the $0$s in the original string. On this basis, we traverse $s$ from right to left. If we encounter a $1$, we check if adding this $1$ to the subsequence keeps the binary number $v \leq k$.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#2472 maximum number of non overlapping palindrome substrings #2522 partition string into substrings with values at most k #2086 minimum number of food buckets to feed the hamsters