Longest Binary Subsequence Less Than or Equal to K

Longest Binary Subsequence Less Than or Equal to K - 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "1001", k = 9

› Output: 4

💡 Note: The longest subsequence is "1001" which equals 9 in decimal (1×8 + 0×4 + 0×2 + 1×1 = 9), and 9 ≤ 9, so length is 4.

Example 2 — Limited by k

$ Input: s = "111", k = 5

› Output: 3

💡 Note: We can take all characters to form "111" = 7, but 7 > 5. We can take "11" = 3 ≤ 5, or "101" = 5 ≤ 5. The longest is "101" with length 3.

Example 3 — All Zeros

$ Input: s = "000", k = 5

› Output: 3

💡 Note: All zeros can be taken since "000" = 0 ≤ 5, giving us length 3.

Constraints

1 ≤ s.length ≤ 1000
s consists only of '0' and '1'
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string s and limit k

Process

Select characters to form valid binary number

Output

Length of longest valid subsequence

Key Takeaway

🎯 Key Insight: Greedily take all zeros first, then add ones while staying within the limit k

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Meta 18

The key insight is to use a greedy approach: take all zeros first (they don't increase the binary value), then greedily add ones while keeping the total value ≤ k. Best approach is the optimized greedy method that processes characters left to right. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and find the longest valid one
Greedy Approach	O(n)	O(1)	Greedily take all zeros first, then add ones while staying within limit
Optimized Greedy with Bit Counting	O(n)	O(1)	Improved greedy approach that processes ones in order of appearance

Brute Force - Try All Subsequences — Algorithm Steps

Generate all 2^n possible subsequences
Convert each binary subsequence to decimal
Check if decimal value ≤ k
Track maximum length of valid subsequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n possible subsequences

Convert

Convert each binary subsequence to decimal

Check

Find longest valid subsequence ≤ k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

long long binaryToDecimal(char* binary) {
    long long decimal = 0;
    int len = strlen(binary);
    for (int i = 0; i < len; i++) {
        if (binary[i] == '1') {
            decimal += (long long)pow(2, len - 1 - i);
        }
    }
    return decimal;
}

int solution(char* s, int k) {
    int n = strlen(s);
    int maxLength = 0;
    
    // Try all possible subsequences using bit manipulation
    for (int mask = 0; mask < (1 << n); mask++) {
        char subsequence[1000] = "";
        int idx = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subsequence[idx++] = s[i];
            }
        }
        subsequence[idx] = '\0';
        
        if (strlen(subsequence) == 0) {
            if (maxLength < 0) {
                maxLength = 0;
            }
            continue;
        }
        
        // Convert binary string to integer
        long long decimalValue = binaryToDecimal(subsequence);
        if (decimalValue <= k) {
            int len = strlen(subsequence);
            if (len > maxLength) {
                maxLength = len;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char s[1000];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

2^n subsequences, each taking O(n) time to process and convert

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing current subsequence during generation

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler