2311. Longest Binary Subsequence Less Than or Equal to K

MediumGreedyMemoizationStringDynamic Programming
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. If both conditions hold true for "1", we update v to include the current bit by setting v |= 1 << ans and increment ans.

  6. 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.

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

Which of the following is a min heap?

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:

  1. 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.

  2. 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").

  3. 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'.

  4. 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
Not Sure What to Study? Take the 2-min Quiz

Which of the following is a min heap?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Memoization

Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«