We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Binary Subsequence Less Than or Equal to K

Number: 2395

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary string s and a positive integer k, return the length of the longest subsequence of s that, when interpreted as a binary number, is less than or equal to k. (A subsequence is formed by deleting zero or more characters without changing the relative order. The subsequence may have leading zeroes, and the empty string is considered to equal 0.)

Key Insights

  • A subsequence’s binary value is computed by treating the chosen bits (in order) as a binary number with the leftmost bit having the highest weight.
  • Zeros are “free” in the sense that if they are placed in the most significant positions (to the left of any one), they do not contribute to the value.
  • However, if a zero is inserted after a one, it increases the overall length and shifts the one(s) to higher (more significant) positions.
  • To minimize the binary value while maximizing length, one would want to include as many characters as possible but “delay” the inclusion of ones (or use only a few ones) so that they fall in positions with lower weight.
  • A useful approach is to use dynamic programming over the original string by processing s from left-to-right and keeping track, for each possible subsequence length, of the minimal binary value that can be achieved.

Space and Time Complexity

Time Complexity: O(n²), where n is the length of s
Space Complexity: O(n), for the DP array

Solution

We use a dynamic programming approach. Define dp[i] as the minimum possible value of some subsequence of s (chosen in order) having length i. Initially, dp[0] is 0 (the empty subsequence) and dp[i] for i ≥ 1 is set to INF (a value larger than any possible valid binary number given the constraints). Then, for each character in s (from left to right), we update dp in reverse order so that we extend all subsequences that have already been formed without interfering with the current iteration. When appending a character c to a subsequence that currently has value v and length L, the new value becomes (v * 2 + (c – '0')). We update dp[L+1] if the new value is ≤ k. Finally, the answer is the maximum length L for which dp[L] ≤ k. This works because by “optimally” tracking the minimum value achievable for each length, we know whether a subsequence of that length can be constructed with a value ≤ k.

Code Solutions

# Python solution with detailed comments

INF = float('inf')

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        n = len(s)
        # dp[length] will hold the minimum binary value achievable with some subsequence of that length.
        dp = [INF] * (n + 1)
        dp[0] = 0  # Empty subsequence has value 0.
        
        # Process each character in s from left to right.
        for char in s:
            # Traverse backwards to ensure we do not update dp values that are needed in the current iteration.
            for length in range(n - 1, -1, -1):
                if dp[length] != INF:
                    # Calculate the new value if we append the current character.
                    new_value = dp[length] * 2 + (1 if char == '1' else 0)
                    # Only update if the new value does not exceed k.
                    if new_value <= k:
                        dp[length + 1] = min(dp[length + 1], new_value)
        # The answer is the maximum length for which a valid subsequence exists.
        max_length = 0
        for length in range(n + 1):
            if dp[length] <= k:
                max_length = length
        return max_length

# Example usage:
# sol = Solution()
# print(sol.longestSubsequence("1001010", 5))  # Expected output: 5
← Back to All Questions