2311. Longest Binary Subsequence ≤ K - Solution

Q: Is Longest Binary Subsequence Less Than or Equal to K easy or hard?

This problem is generally classified as Medium difficulty. The challenge lies in recognizing the greedy property of binary positional weights. Once that insight is clear, the implementation becomes straightforward and runs in linear time.

Q: Longest Binary Subsequence Less Than or Equal to K Python/Java solution

Most implementations use the greedy method. Iterate from the end of the string, track the current value and power-of-two weight, and count valid bits. The same logic translates directly to Python, Java, C++, JavaScript, and other languages with identical O(n) time complexity.

Q: How to solve Longest Binary Subsequence Less Than or Equal to K in O(n)?

Scan the string from right to left while maintaining the current binary value and bit weight. Always include '0' because it increases length without increasing value. For '1', include it only if the resulting value does not exceed k. Stop considering further '1's once the bit weight becomes larger than k.

Q: What is the best approach for Longest Binary Subsequence Less Than or Equal to K?

The greedy right-to-left approach is the most efficient. Traverse the binary string from the end, always include '0', and include '1' only if its positional value keeps the number ≤ k. This works because rightmost bits have the smallest contribution to the final value. The algorithm runs in O(n) time with O(1) extra space.

Q: Is Longest Binary Subsequence Less Than or Equal to K asked at Google/Amazon/Meta?

Problems involving greedy reasoning with binary representation frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. Variants of subsequence selection and binary value constraints are common in medium-level interview rounds.

Q: What data structure is used in Longest Binary Subsequence Less Than or Equal to K?

The greedy solution uses simple variables to track the current value and bit weight while iterating through the string. No complex data structures are required. The alternative dynamic programming approach may use recursion with memoization or a DP table to store intermediate results.

Q: What is the time complexity of Longest Binary Subsequence Less Than or Equal to K?

The optimal greedy solution runs in O(n) time where n is the length of the binary string. It performs a single pass while maintaining the current value and bit weight. A dynamic programming alternative may take O(n * log k) time due to tracking possible values up to the bit length of k.

The problem

You are given a binary string s and a positive integer k.

Return the length of the longest subsequence of s that makes up a binary number less than or equal to k.

Note:

The subsequence can contain leading zeroes.
The empty string is considered to be equal to 0.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

Input: s = "1001010", k = 5
Output: 5
Explanation: The longest subsequence of s that makes up a binary number less than or equal to 5 is "00010", as this number is equal to 2 in decimal.
Note that "00100" and "00101" are also possible, which are equal to 4 and 5 in decimal, respectively.
The length of this subsequence is 5, so 5 is returned.

Example 2:

Input: s = "00101001", k = 1
Output: 6
Explanation: "000001" is the longest subsequence of s that makes up a binary number less than or equal to 1, as this number is equal to 1 in decimal.
The length of this subsequence is 6, so 6 is returned.

Constraints:

1 <= s.length <= 1000
s[i] is either '0' or '1'.
1 <= k <= 10⁹

Approach overview

Problem Overview: You receive a binary string s and an integer k. The task is to pick a subsequence of s that forms a binary number less than or equal to k, while maximizing the subsequence length. The subsequence must preserve order, but you can skip characters.

Approach 1: Dynamic Programming with Memoization (O(n * log k) time, O(n * log k) space)

This approach models the decision process for each index: include the current bit or skip it. The state typically tracks the current position and the value of the binary number formed so far. Because the value grows exponentially with appended bits, you cap the tracked value at k. Use memoization to avoid recomputing overlapping states. Each recursive step branches into two choices and stores the best result. The complexity depends on the maximum number of bits needed to represent k, which is roughly log₂(k). This method is useful when demonstrating classic dynamic programming thinking or when reasoning about subsequences systematically.

Approach 2: Greedy from Right to Left (O(n) time, O(1) space)

The optimal solution relies on a key observation about binary numbers. Bits on the right contribute less to the value than bits on the left. When building the subsequence, you want to include as many low-weight bits as possible. Start scanning from the rightmost character of the string. Keep track of the current value and the bit weight (1, 2, 4, 8...). If adding a '1' keeps the value ≤ k, include it and update the value. Always include '0' because it does not increase the number's value but increases subsequence length. Stop considering '1's once the bit weight exceeds k, since any further '1' would push the value beyond the limit. This greedy logic works because choosing smaller positional weights first maximizes the number of usable bits. The algorithm performs a single pass and uses constant extra memory, making it ideal for interview settings involving greedy algorithms.

Recommended for interviews: The greedy solution is what interviewers typically expect. It shows you understand how binary positional weights affect numeric value and how to exploit that structure for an O(n) pass. Discussing the dynamic programming formulation first can help demonstrate problem‑solving depth, but implementing the greedy approach shows stronger optimization skills.

Approach 1: Greedy Approach

In this approach, we will aim to maximize the count of '0's in the subsequence because they contribute a value of 0 to the binary number, ensuring it stays small. We then try to add as many '1's as we can while ensuring that the binary number formed remains less than or equal to k.

Python

def longestSubsequence(s, k):
    length = 0
    value = 0
    ones_count = 0
    for i in reversed(s):
        if i == '0':
            length += 1
        else: 
            potential_value = value + (1 << ones_count)
            if potential_value <= k:
                value = potential_value
                length += 1
            ones_count += 1
    return length

# Example usage
s = "1001010"
k = 5
print(longestSubsequence(s, k))  # Output: 5

Java

public class Solution {
    public int longestSubsequence(String s, int k) {
        int length = 0;
        long value = 0;
        int onesCount = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                length++;
            } else { // s.charAt(i) == '1'
                long potentialValue = value + (1L << onesCount);
                if (potentialValue <= k) {
                    value = potentialValue;
                    length++;
                }
                onesCount++;
            }
        }
        return length;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestSubsequence("1001010", 5)); // Output: 5
    }
}

C++

#include <iostream>
#include <string>
using namespace std;

int longestSubsequence(string s, int k) {
    int length = 0;
    long long value = 0;
    int onesCount = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s[i] == '0') {
            length++;
        } else { // s[i] == '1'
            long long potentialValue = value + (1LL << onesCount);
            if (potentialValue <= k) {
                value = potentialValue;
                length++;
            }
            onesCount++;
        }
    }
    return length;
}

int main() {
    string s = "1001010";
    int k = 5;
    cout << longestSubsequence(s, k) << endl; // Output: 5
    return 0;
}

JavaScript

function longestSubsequence(s, k) {
    let length = 0;
    let value = 0;
    let onesCount = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] === '0') {
            length++;
        } else { 
            let potentialValue = value + (1 << onesCount);
            if (potentialValue <= k) {
                value = potentialValue;
                length++;
            }
            onesCount++;
        }
    }
    return length;
}

// Example usage
const s = "1001010";
const k = 5;
console.log(longestSubsequence(s, k)); // Output: 5

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int longestSubsequence(char* s, int k) {
    int length = 0;
    long long value = 0;
    int onesCount = 0;
    for (int i = strlen(s) - 1; i >= 0; i--) {
        if (s[i] == '0') {
            length++;
        } else { // s[i] == '1'
            long long potentialValue = value + (1LL << onesCount);
            if (potentialValue <= k) {
                value = potentialValue;
                length++;
            }
            onesCount++;
        }
    }
    return length;
}

int main() {
    char s[] = "1001010";
    int k = 5;
    printf("%d\n", longestSubsequence(s, k)); // Output: 5
    return 0;
}

using System;

public class Solution {
    public int LongestSubsequence(string s, int k) {
        int length = 0;
        long value = 0;
        int onesCount = 0;
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '0') {
                length++;
            } else { 
                long potentialValue = value + (1L << onesCount);
                if (potentialValue <= k) {
                    value = potentialValue;
                    length++;
                }
                onesCount++;
            }
        }
        return length;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.LongestSubsequence("1001010", 5)); // Output: 5
    }
}

Python makes use of its dynamic integer handling capabilities to effectively accumulate the overall binary value produced by valid bits. The iteration is reversed to prioritize adding bits of higher positional magnitude.

Complexity

We analyze each bit thus implicating a time complexity of O(n), where n is the length of string s. Space complexity remains O(1).

Try this approach in the editor

Approach 2: Dynamic Programming Approach (Less Optimal)

This approach leverages dynamic programming to store intermediate results and build up to the final output. It is generally less efficient than the greedy approach but illustrates a bottom-up method of solving the problem.

Python

def longestSubsequence(s, k):
    n = len(s)
    dp = [0] * (n + 1)
    current_value = 0
    power = 1

    for i in range(n):
        dp[i + 1] = dp[i] + (s[i] == '0')
        if s[i] == '1' and current_value + power <= k:
            dp[i + 1] = max(dp[i + 1], dp[i] + 1)
            current_value += power
        power *= 2

    return dp[n]

# Example usage
s = "1001010"
k = 5
print(longestSubsequence(s, k))  # Output: 5

Java

import java.util.Arrays;

public class Solution {
    public int longestSubsequence(String s, int k) {
        int n = s.length();
        int[] dp = new int[n + 1];
        long current_value = 0;
        int power = 1;

        for (int i = 0; i < n; i++) {
            dp[i + 1] = dp[i] + (s.charAt(i) == '0' ? 1 : 0);
            if (s.charAt(i) == '1' && current_value + power <= k) {
                dp[i + 1] = Math.max(dp[i + 1], dp[i] + 1);
                current_value += power;
            }
            power *= 2;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestSubsequence("1001010", 5)); // Output: 5
    }
}

C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int longestSubsequence(string s, int k) {
    int n = s.size();
    vector<int> dp(n + 1, 0);
    long long current_value = 0;
    int power = 1;

    for (int i = 0; i < n; i++) {
        dp[i + 1] = dp[i] + (s[i] == '0');
        if (s[i] == '1' && current_value + power <= k) {
            dp[i + 1] = max(dp[i + 1], dp[i] + 1);
            current_value += power;
        }
        power <<= 1;
    }
    return dp[n];
}

int main() {
    string s = "1001010";
    int k = 5;
    cout << longestSubsequence(s, k) << endl; // Output: 5
    return 0;
}

JavaScript

function longestSubsequence(s, k) {
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    let currentValue = 0;
    let power = 1;

    for (let i = 0; i < n; i++) {
        dp[i + 1] = dp[i] + (s[i] === '0' ? 1 : 0);
        if (s[i] === '1' && currentValue + power <= k) {
            dp[i + 1] = Math.max(dp[i + 1], dp[i] + 1);
            currentValue += power;
        }
        power *= 2;
    }

    return dp[n];
}

// Example usage
const s = "1001010";
const k = 5;
console.log(longestSubsequence(s, k)); // Output: 5

#include <stdio.h>
#include <string.h>
#include <limits.h>

int min(int a, int b) { return a < b ? a : b; }

int longestSubsequence(char * s, int k) {
    int n = strlen(s);
    int dp[n + 1];
    dp[0] = 0;
    long long current_value = 0;
    int power = 1;

    for (int i = 0; i < n; i++) {
        dp[i + 1] = dp[i] + (s[i] == '0');
        if (s[i] == '1' && current_value + power <= k) {
            dp[i + 1] = max(dp[i + 1], dp[i] + 1);
            current_value += power;
        }
        power <<= 1;
    }
    return dp[n];
}

int main() {
    char s[] = "1001010";
    int k = 5;
    printf("%d\n", longestSubsequence(s, k)); // Output: 5
    return 0;
}

using System;

public class Solution {
    public int LongestSubsequence(string s, int k) {
        int n = s.Length;
        int[] dp = new int[n + 1];
        long currentValue = 0;
        int power = 1;

        for (int i = 0; i < n; i++) {
            dp[i + 1] = dp[i] + (s[i] == '0' ? 1 : 0);
            if (s[i] == '1' && currentValue + power <= k) {
                dp[i + 1] = Math.Max(dp[i + 1], dp[i] + 1);
                currentValue += power;
            }
            power *= 2;
        }
        return dp[n];
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.LongestSubsequence("1001010", 5)); // Output: 5
    }
}

Python empowers iterator-based variable control, fostering extensive trial generation via power multipliers and axis-condensed dp tables but generally found suboptimal for this type of problem.

Complexity

Processor time requires O(n^2) enactment intervals, plus likewise spatial O(n) for tablet enumerations, over extensions resembling linear aggregates.

Try this approach in the editor

Approach 3: Greedy

The longest binary subsequence must include all the 0s in the original string. On this basis, we traverse s from right to left. If we encounter a 1, we check if adding this 1 to the subsequence keeps the binary number v leq k.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

TypeScript

function longestSubsequence(s: string, k: number): number {
    let ans = 0;
    for (let i = s.length - 1, v = 0; ~i; --i) {
        if (s[i] == '0') {
            ++ans;
        } else if (ans < 30 && (v | (1 << ans)) <= k) {
            v |= 1 << ans;
            ++ans;
        }
    }
    return ans;
}

func longestSubsequence(s string, k int) (ans int) {
	for i, v := len(s)-1, 0; i >= 0; i-- {
		if s[i] == '0' {
			ans++
		} else if ans < 30 && (v|1<<ans) <= k {
			v |= 1 << ans
			ans++
		}
	}
	return
}

Rust

impl Solution {
    pub fn longest_subsequence(s: String, k: i32) -> i32 {
        let mut ans = 0;
        let mut v = 0;
        let s = s.as_bytes();
        for i in (0..s.len()).rev() {
            if s[i] == b'0' {
                ans += 1;
            } else if ans < 30 && (v | (1 << ans)) <= k {
                v |= 1 << ans;
                ans += 1;
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	We analyze each bit thus implicating a time complexity of O(n), where n is the length of string s. Space complexity remains O(1).
Dynamic Programming Approach (Less Optimal)	Processor time requires O(n^2) enactment intervals, plus likewise spatial O(n) for tablet enumerations, over extensions resembling linear aggregates.
Greedy	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Memoization	O(n * log k)	O(n * log k)	When exploring all subsequence decisions or explaining a systematic DP formulation
Greedy Right-to-Left Bit Selection	O(n)	O(1)	Best choice for interviews and large inputs where a single linear pass is required

Frequently asked questions

Is Longest Binary Subsequence Less Than or Equal to K easy or hard?

This problem is generally classified as Medium difficulty. The challenge lies in recognizing the greedy property of binary positional weights. Once that insight is clear, the implementation becomes straightforward and runs in linear time.

Longest Binary Subsequence Less Than or Equal to K Python/Java solution

Most implementations use the greedy method. Iterate from the end of the string, track the current value and power-of-two weight, and count valid bits. The same logic translates directly to Python, Java, C++, JavaScript, and other languages with identical O(n) time complexity.

How to solve Longest Binary Subsequence Less Than or Equal to K in O(n)?

Scan the string from right to left while maintaining the current binary value and bit weight. Always include '0' because it increases length without increasing value. For '1', include it only if the resulting value does not exceed k. Stop considering further '1's once the bit weight becomes larger than k.

What is the best approach for Longest Binary Subsequence Less Than or Equal to K?

The greedy right-to-left approach is the most efficient. Traverse the binary string from the end, always include '0', and include '1' only if its positional value keeps the number ≤ k. This works because rightmost bits have the smallest contribution to the final value. The algorithm runs in O(n) time with O(1) extra space.

Is Longest Binary Subsequence Less Than or Equal to K asked at Google/Amazon/Meta?

Problems involving greedy reasoning with binary representation frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. Variants of subsequence selection and binary value constraints are common in medium-level interview rounds.

What data structure is used in Longest Binary Subsequence Less Than or Equal to K?

The greedy solution uses simple variables to track the current value and bit weight while iterating through the string. No complex data structures are required. The alternative dynamic programming approach may use recursion with memoization or a DP table to store intermediate results.

What is the time complexity of Longest Binary Subsequence Less Than or Equal to K?

The optimal greedy solution runs in O(n) time where n is the length of the binary string. It performs a single pass while maintaining the current value and bit weight. A dynamic programming alternative may take O(n * log k) time due to tracking possible values up to the bit length of k.

Longest Binary Subsequence Less Than or Equal to K solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Dynamic Programming Approach (Less Optimal)

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Binary Subsequence Less Than or Equal to K solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Dynamic Programming Approach (Less Optimal)

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems