Problem of The Day: Longest Binary Subsequence Less Than or Equal to K

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        N = len(s)
        res = 0
        for i in range(N - 1, -1, -1):
            curr = deque()
            curr.appendleft(s[i])
            for j in range(i - 1, -1, -1):
                curr.appendleft(s[j])
                if int(''.join(curr), 2) <= k:
                    continue
                else:
                    curr.popleft()
            res = max(res, len(curr))
        return res

Improved Algorithm [Accepted]

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        list_chars = list(s)
        removed_indices = set()
        N = len(s)
        res = 0
        for i in range(N):
            temp = []
            for j, x in enumerate(list_chars):
                if j in removed_indices:
                    continue
                temp.append(x)

            if int(''.join(temp), 2) <= k:
                return len(temp)
            else:
                if list_chars[i] == "1":
                    removed_indices.add(i)
        return res

Editorial

Approach: Greedy

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        sm = 0
        cnt = 0
        bits = k.bit_length()
        for i, ch in enumerate(s[::-1]):
            if ch == "1":
                if i < bits and sm + (1 << i) <= k:
                    sm += 1 << i
                    cnt += 1
            else:
                cnt += 1
        return cnt