2311. Longest Binary Subsequence Less Than or Equal to K

MediumGreedyMemoizationStringDynamic Programming

Problem Description

In this problem, you are given a binary string s which only consists of 0s and 1s. You are also given a positive integer k. The task is to find the length of the longest subsequence of the given binary string s such that when the subsequence is treated as a binary number, it is less than or equal to k. There are a couple of extra points to keep in mind:

Leading zeroes in the subsequence are allowed.
An empty subsequence is considered as binary 0.
A subsequence can be derived from the string by deleting some or no characters without changing the order of the remaining characters.

To clarify, a binary string is a sequence of bits (where each bit is either 0 or 1). The length of a subsequence is the total number of bits it contains.

Intuition

For solving this problem, we start thinking about the properties of binary numbers. A crucial observation is that the least significant bits have the least effect on the value of the binary number. For example, in binary 1011, if we drop the last 1, the number changes from 11 (in decimal: 3) to 1010 (in decimal: 10), which is a much smaller change compared to dropping a higher bit.

Given that we can only choose subsequences (i.e., we can't rearrange the bits), the logical approach is to consider bits from the least significant to the most significant (from right to left in the string) and decide whether to include them in our subsequence.

One key insight is to realize that we should always take as many 0s as possible because they do not increase the value of our number. On the other hand, taking a 1 would increase the value, so we should only take a 1 if it doesn't cause the subsequence to exceed k. Also, we should process the string in reverse to ensure we are considering the bits from low to high significance.

Another detail is that because integer values can only be accurately represented in most programming languages up to a certain limit (typically 32 bits for a signed int in many languages), and because k can be at most 10^9, we only need to consider the last 30 bits of any subsequence when determining if its value is less than or equal to k. This significantly simplifies the problem because we don't need to work with potentially very long binary strings; we can ignore any bits past the 30th most significant bit.

The provided code snippet shows an efficient realization of these ideas. It initializes a counter ans to keep track of the length of our subsequence and a value v which is the decimal representation of the subsequence being constructed. It iterates over the binary string s in reverse. When it encounters a 0, it can safely include it, so it increments the ans. When it encounters a 1, it checks whether including this 1 would keep the value v under k. If so, it sets the corresponding bit in v (using bitwise OR and bitwise shift operations) and increments ans. For this check, it also makes sure that the number of bits processed is less than 30 to avoid overflow issues.

By the end of this process, ans holds the maximum length of a subsequence that represents a number less than or equal to k.

Learn more about Greedy, Memoization and Dynamic Programming patterns.

Solution Approach

The implementation of the solution is quite straightforward once the intuition is understood.

Here's a step-by-step breakdown of the implemented code:

Initialize two variables:
- ans set to 0, which will ultimately contain the length of the longest valid subsequence.
- v set to 0, which will keep track of the current numeric value of the subsequence being considered in decimal.
Loop through the binary string in reverse order using for c in s[::-1]:. This ensures that we examine bits from least significant to most significant.
Inside the loop, check if the current character c is "0":
- If that's the case, since a zero does not change the current value of v but can still be part of the subsequence, increment ans by 1.
If the character is "1", there are two conditions to check:
- First, check if the length of the subsequence is less than 30 (ans < 30). This is important to prevent overflow and because we are only interested in subsequences that can affect the value within the integer limit, as explained in the intuition part.
- Second, we want to make sure that by setting the current bit (which we obtain by 1 << ans) the value of v would still be less than or equal to k. This is done by the operation (v | 1 << ans) <= k, which uses a bitwise OR (|) coupled with a left shift (<<) to add the current bit to v.
If both conditions hold true for "1", we update v to include the current bit by setting v |= 1 << ans and increment ans.
Once the loop finishes, ans would have the length of the longest valid subsequence by iteratively building it from the lowest order bit towards the highest order bit considered, ensuring that at any time the subsequence's value does not exceed k.

The code uses a bitwise approach to manipulate and evaluate the binary numbers without converting them to their decimal counterparts. This pattern leverages the efficiency of bitwise operations and keeps the implementation clean and straightforward.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the following scenario:

binary string s = "10101"
integer k = 5 (binary representation: "101")

We aim to find the longest subsequence of s that, when treated as a binary number, does not exceed k (5 in decimal). Following the steps from the solution approach:

Initialize ans to 0 and v to 0. ans will track the length of our subsequence, and v will track the numeric value of the subsequence as we build it.
Process the binary string in reverse. Our string s is "10101", so we start from the last character and move to the first (i.e., "10101" -> "10101").
The string in reverse is "10101", which we process from left to right:
- 1st char ('1'): ans is 0, so 1 << ans is 1. We can't include this '1' because v | 1 would become 1, which is not less than or equal to k (5).
- 2nd char ('0'): We include this zero because adding zeros doesn't change the value. Now, ans is incremented to 1.
- 3rd char ('0'): Include this zero as well, increment ans to 2.
- 4th char ('1'): Check if ans is less than 30 and if (v | 1 << ans) <= k. ans is 2, so 1 << ans equals 4, and the current v is 0. The result of v | 4 is 4, which is less than or equal to k (5), so include this '1' and increment ans to 3.
- 5th char ('1'): Now ans is 3, so 1 << ans equals 8, and the current v is 4. v | 8 would be 12, which exceeds k. Therefore, we cannot include this '1'.
The loop ends with ans equal to 3. The subsequence that we can form is "001" (when read in the original order it's "100"), which equals 4 in decimal, and is less than or equal to k.

The longest valid subsequence of the original binary string "10101", which represents a value less than or equal to 5, is "100" (in the subsequence order it's "001"), and its length is 3. Therefore, our ans is 3, which is the final result.

Solution Implementation

1class Solution:
2    def longestSubsequence(self, s: str, k: int) -> int:
3        # Initialize the count of the subsequence and the value of the binary string seen so far
4        subsequence_length = value_so_far = 0
5      
6        # Iterate over the string in reverse order since the least significant bit contributes less to the overall value
7        for character in reversed(s):
8            # If the character is '0', it doesn't affect the value but can increase the length of the subsequence
9            if character == "0":
10                subsequence_length += 1
11            # If the character is '1', check if adding this bit exceeds the value of k
12            # Since we're looking at the binary string from right to left, we shift 1 left by the current subsequence length
13            # The subsequence_length represents the binary digit's position (0-indexed)
14            # Also note that we perform this check only if subsequence_length is less than 30 since 2^30 is the first power of 2 that exceeds 10^9 (~2^30.103). k is less than or equal to 10^9
15            elif subsequence_length < 30 and (value_so_far | (1 << subsequence_length)) <= k:
16                # If adding '1' to the current position does not exceed k, update the value_so_far
17                value_so_far |= 1 << subsequence_length
18                # Increase subsequence_length as this '1' is part of the longest subsequence not exceeding k
19                subsequence_length += 1
20              
21        # Return the length of the longest subsequence not exceeding the value k
22        return subsequence_length
23

1class Solution {
2
3    /**
4     * Returns the length of the longest subsequence with a decimal value less than or equal to k.
5     *
6     * @param s The binary string.
7     * @param k The upper bound for decimal value of the subsequence.
8     * @return The length of the longest subsequence.
9     */
10    public int longestSubsequence(String s, int k) {
11        int longestLength = 0; // The length of the longest valid subsequence
12        int decimalValue = 0;  // The decimal value of the considered subsequence
13
14        // Iterate over the string in reverse because the least significant bits
15        // can be considered in isolation for the smallest possible addition to the value.
16        for (int index = s.length() - 1; index >= 0; --index) {
17            // If we find a '0', it doesn't add to the value,
18            // so we can always include it in the subsequence
19            if (s.charAt(index) == '0') {
20                ++longestLength;
21            }
22            // Only consider '1's if the length of the sequence is less than 30
23            // and adding the '1' wouldn't exceed k. We check length < 30
24            // because 2^30 exceeds Integer.MAX_VALUE and cannot be represented by int.
25            else if (longestLength < 30 && (decimalValue | (1 << longestLength)) <= k) {
26                // '|' is the bitwise OR operator. Here we add the value represented by
27                // a '1' at the current position to the decimalValue (if it does not exceed k).
28                decimalValue |= 1 << longestLength;
29                // Increment the length because we've added a '1' to the subsequence.
30                ++longestLength;
31            }
32        }
33        return longestLength; // Return the computed length of the longest subsequence
34    }
35}
36

1class Solution {
2public:
3    int longestSubsequence(string s, int k) {
4        int answer = 0;         // Used to track the length of the longest subsequence
5        int value = 0;          // Used to store the current value of the binary subsequence
6        // Loop through the string backwards to consider the least significant bits first
7        for (int i = s.size() - 1; i >= 0; --i) {
8            if (s[i] == '0') {
9                // If the current character is '0', we can always include it without
10                // affecting the value of the binary number it represents.
11                ++answer;
12            } else if (answer < 30 && (value | (1 << answer)) <= k) {
13                // Check if the current length of the subsequence is less than 30
14                // (Because 2^30 is the first number larger than 10^9, which is outside the constraint for k)
15                // and if by setting the current bit to 1 we still get a value less than or equal to k.
16                // 1 << answer is the value of setting the current bit (at position 'answer') to 1.
17                value |= 1 << answer;  // Set the current bit to 1.
18                ++answer;              // Increment the length of the longest subsequence.
19            }
20            // If the bit is '1' and including it would make the value exceed k or
21            // the length of the subsequence is already equal or longer than 30, skip it.
22        }
23        return answer;  // Return the length of the longest subsequence found.
24    }
25};
26

1function longestSubsequence(s: string, k: number): number {
2    let longestLength = 0; // Initialize the longest subsequence length to 0
3    let currentValue = 0; // Initialize the current value of the binary subsequence to 0
4
5    // Traverse the string from right to left (least significant bit to most significant bit)
6    for (let index = s.length - 1; index >= 0; --index) {
7        // If the character at the current index is '0', it doesn't contribute to the value
8        // of the binary number, so we can safely include it without worrying about the
9        // value exceeding `k`, and increment the length of the subsequence.
10        if (s[index] == '0') {
11            longestLength++;
12        } else {
13            // If the character is '1' and the length of the subsequence is less than 30
14            // (since 2^30 exceeds JavaScript's safe integer for bitwise operations),
15            // and the value of including this '1' does not exceed k, include it
16            // in the subsequence. The use of `<= k` is crucial since `k` is inclusive.
17            if (longestLength < 30 && (currentValue | (1 << longestLength)) <= k) {
18                currentValue |= 1 << longestLength; // Include '1' in the currentValue.
19                longestLength++; // Increment the subsequence length after including '1'.
20            }
21        }
22    }
23    // Return the length of the longest subsequence that satisfies the condition.
24    return longestLength;
25}
26

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the input string s. The reason for this is that the code consists of a single loop that traverses the string in reverse, performing a constant amount of work for each character. There are no nested loops, recursive calls, or operations that would increase the complexity beyond linear.

Space Complexity

The space complexity of the code is O(1) because it uses a fixed amount of additional space regardless of the input size. Variables ans and v are the only variables that occupy space and their space requirement does not scale with the input string's length. The input string s and integer k are given, and we do not allocate any additional space that is dependent on the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems