Ones and Zeroes - Practice Coding Problems

Ones and Zeroes - Problem

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m zeros ('0's) and n ones ('1's) in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Input & Output

Example 1 — Basic Case

$ Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3

› Output: 4

💡 Note: We can select at most 4 strings: "10" (1 zero, 1 one), "0001" (3 zeros, 1 one), "1" (0 zeros, 1 one), "0" (1 zero, 0 ones). Total: 5 zeros, 3 ones, which fits exactly within our limits.

Example 2 — Tight Constraints

$ Input: strs = ["10","0","1"], m = 1, n = 1

› Output: 2

💡 Note: With only 1 zero and 1 one allowed, we can take either "10" (1 zero, 1 one) for count=1, OR "0" + "1" (1 zero, 1 one total) for count=2. The second option is better.

Example 3 — Edge Case

$ Input: strs = ["111","1000"], m = 3, n = 1

› Output: 1

💡 Note: "111" has 3 ones but we only have budget for 1 one. "1000" has 3 zeros and 1 one, fits our constraints. Answer is 1.

Constraints

1 ≤ strs.length ≤ 600
1 ≤ strs[i].length ≤ 100
strs[i] consists only of digits '0' and '1'
1 ≤ m, n ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array of binary strings with zero/one budget limits

Count Characters

Each string consumes specific zeros and ones

Maximize Subset

Find largest subset fitting within budget

Key Takeaway

🎯 Key Insight: This is a 2D knapsack where each item has two costs and we maximize item count

Asked in

G Google 28 f Facebook 15 M Microsoft 12 a Amazon 8

This is a 3D knapsack problem where each string has two costs (zeros and ones) and we want to maximize the count of items taken. The key insight is to use 2D dynamic programming where dp[i][j] represents the maximum number of strings achievable with at most i zeros and j ones. Best approach is 2D DP with Time: O(k×m×n), Space: O(m×n).

Common Approaches

Approach	Time	Space	Notes
✓ Recursion with Memoization	O(k × m × n)	O(k × m × n)	Cache recursive results to avoid redundant calculations
2D Dynamic Programming	O(k × m × n + L)	O(m × n)	Build 2D table iteratively for optimal substructure
Recursive Brute Force	O(2^k × L)	O(k)	Try all possible subsets and find the largest valid one

Recursion with Memoization — Algorithm Steps

Define recursive function with state (index, zeros_left, ones_left)
Use memoization to cache results for each state
For each string, decide whether to include or skip it
Return cached result if state already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Cache

Look up current state in memo table

Compute & Store

If not cached, compute result and store

Reuse Results

Future calls to same state return cached value

Code -

solution.c — C

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

#define MAX_STATES 100000

struct MemoEntry {
    int index, zerosLeft, onesLeft, result;
};

struct MemoEntry memoTable[MAX_STATES];
int memoSize = 0;

void countZerosOnes(const char* s, int* zeros, int* ones) {
    *zeros = 0;
    *ones = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '0') (*zeros)++;
        else if (s[i] == '1') (*ones)++;
    }
}

int findMemo(int index, int zerosLeft, int onesLeft) {
    for (int i = 0; i < memoSize; i++) {
        if (memoTable[i].index == index && memoTable[i].zerosLeft == zerosLeft && memoTable[i].onesLeft == onesLeft) {
            return memoTable[i].result;
        }
    }
    return -1;
}

void addMemo(int index, int zerosLeft, int onesLeft, int result) {
    if (memoSize < MAX_STATES) {
        memoTable[memoSize].index = index;
        memoTable[memoSize].zerosLeft = zerosLeft;
        memoTable[memoSize].onesLeft = onesLeft;
        memoTable[memoSize].result = result;
        memoSize++;
    }
}

int dp(char strs[][101], int len, int index, int zerosLeft, int onesLeft) {
    if (index == len) {
        return 0;
    }
    
    int cached = findMemo(index, zerosLeft, onesLeft);
    if (cached != -1) {
        return cached;
    }
    
    // Skip current string
    int result = dp(strs, len, index + 1, zerosLeft, onesLeft);
    
    // Try including current string
    int zeros, ones;
    countZerosOnes(strs[index], &zeros, &ones);
    if (zeros <= zerosLeft && ones <= onesLeft) {
        int included = 1 + dp(strs, len, index + 1, zerosLeft - zeros, onesLeft - ones);
        if (included > result) {
            result = included;
        }
    }
    
    addMemo(index, zerosLeft, onesLeft, result);
    return result;
}

int solution(char strs[][101], int len, int m, int n) {
    memoSize = 0;
    return dp(strs, len, 0, m, n);
}

int main() {
    char strs[600][101];
    int len = 0;
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    char* start = strchr(line, '[');
    char* end = strrchr(line, ']');
    start++;
    *end = '\0';
    
    char* token = strtok(start, ",");
    while (token != NULL) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        char* endQuote = strrchr(token, '"');
        if (endQuote) *endQuote = '\0';
        strcpy(strs[len++], token);
        token = strtok(NULL, ",");
    }
    
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    printf("%d\n", solution(strs, len, m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × m × n)

k strings × m possible zeros × n possible ones, each state computed once due to memoization

✓ Linear Growth

Space Complexity

O(k × m × n)

Memoization table stores results for k × m × n states plus recursion stack

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

3.8K 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

Recursion with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler