LeetCode 2311 - Longest Binary Subsequence Less Than or Equal to K

LeetCode Problem 2311

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Greedy, Memoization

Solution

Problem Understanding

The problem asks us to find the length of the longest subsequence of a given binary string s such that the resulting binary number is less than or equal to a given integer k. A subsequence is any selection of characters from s in their original order, possibly skipping some. Importantly, leading zeros are allowed, and an empty string counts as 0.

The input consists of a string s of length up to 1000, where each character is either '0' or '1', and an integer k that can be as large as 10^9. The output is an integer representing the maximum length of a valid subsequence.

Key points to note include the allowance of leading zeros, the fact that subsequences do not need to be contiguous, and that the binary number formed must not exceed k. Edge cases that might trip up a naive implementation include strings with all zeros, very large values of k, or strings with mostly ones where including all ones would exceed k.

Approaches

A brute-force approach would be to generate all possible subsequences of s, convert each to a decimal integer, check if it is less than or equal to k, and track the maximum length. While this is correct, it is extremely slow, because a string of length n has 2^n possible subsequences, and n can be up to 1000, making this computationally infeasible.

The optimal approach leverages a greedy strategy. Since zeros do not increase the decimal value, we can always include all zeros in the subsequence. For ones, we need to be careful because they increase the decimal value. We iterate from the least significant bit to the most significant bit (i.e., from right to left in the string). We attempt to add ones one by one, keeping track of the decimal value. If adding a one would exceed k, we skip it. This allows us to maximize the length while ensuring the resulting binary number remains valid.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Generates all subsequences, checks each against k
Optimal (Greedy)	O(n)	O(1)	Counts zeros and adds ones from LSB to MSB until reaching k

Algorithm Walkthrough

1. Initialize a counter count for zeros and ones that can safely be included.
2. Initialize a variable value to track the decimal value of the selected ones.
3. Iterate backwards through s from rightmost to leftmost character.
4. If the character is '0', increment count because zeros do not increase the number.
5. If the character is '1', compute the potential new value if this one were included, considering its bit position relative to the LSB of the subsequence.
6. If including the one does not make value exceed k, increment count and update value.
7. Otherwise, skip this one, since including it would exceed k.
8. After iterating through the string, count represents the length of the longest valid subsequence.

Why it works: The greedy strategy works because zeros never increase the binary value, so we can always include them. Processing ones from least significant to most significant ensures we prioritize including ones that contribute less to the decimal value first, allowing more characters in total without exceeding k.

Python Solution

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        n = len(s)
        count = 0
        value = 0
        power = 1

        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                count += 1
            else:
                if value + power <= k:
                    value += power
                    count += 1
                power <<= 1  # Multiply by 2 for next bit
        return count

Explanation: We iterate from the least significant bit (rightmost character) to the most significant. For zeros, we increment count directly. For ones, we check if including the current power of two would exceed k. If not, we include it and update the total value. The power variable doubles each iteration to represent the next higher bit. This guarantees that the resulting subsequence stays within the limit k.

Go Solution

func longestSubsequence(s string, k int) int {
    n := len(s)
    count := 0
    value := 0
    power := 1

    for i := n - 1; i >= 0; i-- {
        if s[i] == '0' {
            count++
        } else {
            if value + power <= k {
                value += power
                count++
            }
            if power <= (1<<30) { // prevent overflow
                power <<= 1
            }
        }
    }
    return count
}

Explanation: The Go version is similar to Python. One difference is the explicit check to prevent integer overflow when shifting power. Go does not automatically handle big integers, so we ensure power stays within bounds while iterating from the rightmost bit to the leftmost.

Worked Examples

Example 1: s = "1001010", k = 5

Iterating right to left:

i	s[i]	value	count	power
6	0	0	1	1
5	1	1	2	2
4	0	1	3	4
3	1	1	3	8 (skip, 1+8>5)
2	0	1	4	16
1	0	1	5	32
0	1	1	5	64

Result: count = 5

Example 2: s = "00101001", k = 1

Iterating right to left:

i	s[i]	value	count	power
7	1	1	1	1
6	0	1	2	2
5	0	1	3	4
4	1	1	3	8 (skip)
3	0	1	4	16
2	1	1	4	32 (skip)
1	0	1	5	64
0	0	1	6	128

Result: count = 6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the string once, performing constant time operations per character
Space	O(1)	Only a few integer variables are used, independent of string length

The algorithm is efficient for the given constraints because n is up to 1000, and all operations are linear and memory-light.

Test Cases

# Provided examples
assert Solution().longestSubsequence("1001010", 5) == 5  # mixture of zeros and ones
assert Solution().longestSubsequence("00101001", 1) == 6  # mostly zeros, k = 1

# Edge cases
assert Solution().longestSubsequence("0", 1) == 1  # single zero
assert Solution().longestSubsequence("1", 1) == 1  # single one, equal to k
assert Solution().longestSubsequence("1", 0) == 0  # single one, cannot include
assert Solution().longestSubsequence("1111111111", 1023) == 10  # all ones, sum within k
assert Solution().longestSubsequence("1111111111", 5) == 3  # all ones, can only include smallest bits
assert Solution().longestSubsequence("0000000", 1) == 7  # all zeros, include all

Test	Why
"1001010", 5	Typical mixture of zeros and ones
"00101001", 1	Mostly zeros, k very small
"0", 1	Minimal input, zero only
"1", 1	Minimal input, one equal to k
"1", 0	Minimal input, one greater than k
"1111111111", 1023	Large all ones, fits within k
"1111111111", 5	Large all ones, cannot include all
"0000000", 1	Large all zeros, include all

Edge Cases

One important edge case is when the string contains only zeros.