Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Leading zeros increase a subsequence's length without increasing its value. Among ones, using positions farther right keeps their place values smaller. If k has b bits, the last b - 1 bits of the source always fit, while only the next bit can make that suffix exceed k.

Approach

Compute k's bit length and scan the source right to left. Within the last b positions, accumulate their original positional values and count a character whenever the suffix value remains at most k. A rejection can occur only at the highest of these positions, so the code does not need to undo its accumulated value afterward. Beyond this width, count only zeros, which become leading zeros of the chosen subsequence. Return the selected length. Keeping a more expensive earlier one cannot improve the length by sacrificing cheaper suffix characters.

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        bits = 0
        num = k

        while num:
            num //= 2
            bits += 1

        res = 0
        curr = 0

        for i, c in enumerate(s[::-1]):
            if i < bits:
                curr += int(c) << i
                if curr <= k:
                    res += 1
            elif c == '0':
                res += 1

        return res

Complexity analysis

Let n = s.length. Time: O(n + log k) to determine the relevant bit width and scan the string from right to left. Auxiliary space: O(n) because the displayed implementations materialize a reversed character sequence.