What is the time complexity of LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K?

The Python solution on this page runs in O(n), where n is the length of the string s.

What is the space complexity of LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K?

The Python solution on this page uses O(1) auxiliary space.

Longest Binary Subsequence Less Than or Equal to K — LeetCode 2311 Python Solution

MediumGreedyMemoizationStringDynamic Programming

Problem: #2311
Pattern: Greedy
Reading time: 2 min
Source: leetcode.com

The problem

You are given a binary string s and a positive integer k. Return the length of the longest subsequence of s that makes up a binary number less than or equal to k.

Example

Input: s = "1001010", k = 5
Output: 5
Explanation: 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.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n), where n is the length of the string s
Space	O(1) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K?: LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K is rated Medium on LeetCode.
What is the time complexity of LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K?: The Python solution on this page runs in O(n), where n is the length of the string s.
What is the space complexity of LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K cover?: LeetCode 2311. Longest Binary Subsequence Less Than or Equal to K is tagged Greedy, Memoization, String and Dynamic Programming on LeetCode.