Ones and Zeroes
Problem Statement
You are given an array strs of binary strings and two integers m and n. Return the size of the largest subset of strs with at most m zeroes and at most n ones. Each string can be used at most once.
Input
An array of binary strings strs, a zero budget m, and a one budget n.
Output
An integer: the maximum number of strings that can be selected without exceeding either budget.
Constraints
- •
1 <= strs.length <= 600 - •
1 <= strs[i].length <= 100 - •
strs[i] consists only of 0 and 1 - •
1 <= m, n <= 100
Examples
Example 1
strs = ['10','0001','111001','1','0'], m = 5, n = 3
4Example 2
strs = ['10','0','1'], m = 1, n = 1
2Example 3
strs = ['10','0001','111001'], m = 3, n = 4
1Learning Objectives
- Extend 0/1 knapsack from one capacity to two capacities: zeroes and ones.
- Precompute each string's resource cost before updating the DP table.
- Scan both capacity dimensions descending so the current string cannot be reused.
- Interpret **dp[z][o]** as a best subset size under two simultaneous budgets.
Intuition
Each string is an item. Its value is 1 because selecting it increases the subset size by one. Its cost is two-dimensional: a number of zeroes and a number of ones. We want the maximum value without exceeding either capacity.
That is still knapsack. The only difference is that capacity is now a grid instead of a line. A state dp[z][o] answers: with zero budget z and one budget o, what is the largest number of strings we can keep from the prefix processed so far?
Because every string can be chosen at most once, both capacity loops must go downward. If either axis went upward, the same string could update a smaller state and then be read again for a larger state in the same outer iteration. Descending in both dimensions preserves the previous item row, exactly like 1D 0/1 knapsack.
Common mistakes
- ×Using ascending loops for zeroes or ones and accidentally selecting the same string multiple times.
- ×Counting the string length as one capacity instead of separating zeroes and ones.
- ×Treating **m** and **n** as exact requirements rather than upper bounds.
- ×Using a 3D table over string index, zeroes, and ones when a descending 2D table is enough.
State Definition
Let dp[z][o] be the maximum number of strings selectable from the processed prefix using at most z zeroes and at most o ones. The answer is dp[m][n].
State Transition
For a string with zeroCost zeroes and oneCost ones, either skip it or take it if both budgets can pay the cost.
The recurrence is dp[z][o] = max(dp[z][o], 1 + dp[z - zeroCost][o - oneCost]) for z >= zeroCost and o >= oneCost.
All states start at 0, meaning the empty subset is always valid. Scan z from m down to zeroCost and o from n down to oneCost. The double descending loop is the two-capacity version of 0/1 knapsack compression.
Solutions
Solution: 2D 0/1 knapsack DP
Count zeroes and ones for each string, then update a 2D capacity table from high budgets down to low budgets. Each update asks whether taking the current string improves the best subset size for that budget pair.
Step-by-step
- Create dp[m + 1][n + 1] initialised to 0.
- For each string, count its zeroes and ones.
- Iterate zeroCap from m down to the string's zero count.
- For each zero capacity, iterate oneCap from n down to the string's one count.
- Update the state by either skipping the string or taking it on top of the remaining budgets.
- Return dp[m][n].
O(strs.length · m · n · L)
O(m · n)
L is the average string length used to count zeroes and ones; the DP update is O(strs.length · m · n).
Java implementation
Dry Run
Sample input
strs = ['10', '0001', '111001', '1', '0'], m = 5, n = 3. Track the best value at the full budget and the decisive states.
| string | zeroes, ones | best at (5,3) | important state after processing |
|---|---|---|---|
| 10 | 1, 1 | 1 | Any budget with at least 1 zero and 1 one can select one string. |
| 0001 | 3, 1 | 2 | State (4,2) becomes 2 by taking 10 and 0001. |
| 111001 | 2, 4 | 2 | It needs 4 ones, so it cannot fit within one budget 3. |
| 1 | 0, 1 | 3 | State (4,3) becomes 3 by adding 1 to 10 and 0001. |
| 0 | 1, 0 | 4 | State (5,3) becomes 4 by adding 0 to the previous best at (4,3). |
The best subset at full capacity uses exactly 5 zeroes and 3 ones: 10, 0001, 1, and 0. Descending updates ensure each of those strings is counted once.
Complexity Analysis
This is the standard 0/1 knapsack compression with two capacity axes. The memory drops from an item-indexed 3D table to a 2D table because both axes are scanned descending.
2D 0/1 knapsack DP
O(strs.length · m · n · L)
O(m · n)
L is the average string length used to count zeroes and ones; the DP update is O(strs.length · m · n).
Interview Tips
Frame each string as an item with value 1 and two costs. Then stress that both capacity loops go downward. If an interviewer asks why, use the same explanation as 1D 0/1 knapsack: the current item must read from the previous row, not from states it just updated.
Likely follow-ups
- Return one largest subset, not just its size.
- What if each string had a different value instead of value 1?
- How would you handle three resource capacities instead of two?
- What if strings could be reused unlimited times?
Similar Problems
Key Takeaways
- Ones and Zeroes is 0/1 knapsack with two capacity dimensions.
- Each string has value 1 and costs equal to its zero and one counts.
- Both capacity loops must scan descending to avoid reusing the current string.
- A 2D table is enough because descending updates preserve the previous item row.