2311. Longest Binary Sequence Less Than K

Problem Statement in English

You’re given a binary string s and an integer k. Your task is to find the length of the longest subsequence of s such that the value of the subsequence, when interpreted as a binary number, is less than k.

Approach

My approach is not optimal. However, I feel it’s really intuitive and easy to understand.

There’s a couple things to note:

• to minimise a binary number, we want to ensure that we pick as many 0s as possible, since 0s contribute nothing to the value of the binary number
• when we do pick a 1, we want to ensure that these 1s are as far to the right as possible, so that they contribute the least to the value of the binary number

So if we assume that we are starting from the right side of a potential binary string, and as we go left, we prepend 1s to the MSB, we can calculate the value of the binary number at each step.

And that’s pretty much it.

Solution in Python

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        def calc(i):
            temp = k
            place = 0

            for j in reversed(range(i + 1)):
                if s[j] == "0":
                    val = 0
                else:
                    val = pow(2, place)

                if temp - val >= 0:
                    temp -= val
                    place += 1

            return place

        ans = 0

        for i in range(len(s)):
            ans = max(ans, calc(i))

        return ans

Complexity

• Time: $O(n^2)$
  Where $n$ is the length of the string s. This is because we iterate through each character in s and for each character, we calculate the value of the binary number formed by the subsequence ending at that character.

• Space: $O(1)$
  Since we only use a few variables to store intermediate results, the space complexity is constant.

And we are done.