378. Ones and Zeroes
You receive an array of binary strings strs (every character is '0' or '1') together with two integers m and n: a budget of m zero-characters and n one-characters.
Pick a subset of the strings so that, summed over everything you pick, the subset uses at most m zeros and at most n ones. Return the largest number of strings such a subset can contain.
Strings are spent whole — you cannot take part of a string — and each string may be picked at most once.
Example 1:
Input: strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
Output: 4
Explanation: Picking {"10", "0001", "1", "0"} spends exactly 5 zeros and 3 ones, so 4 strings fit. No subset of 5 strings stays within the budget.
Example 2:
Input: strs = ["10", "0", "1"], m = 1, n = 1
Output: 2
Explanation: {"0", "1"} uses 1 zero and 1 one. Adding "10" as well would need 2 zeros and 2 ones — over budget — so 2 is the best.
Constraints:
- 1 ≤ strs.length ≤ 600
- 1 ≤ strs[i].length ≤ 100
- strs[i] consists only of the characters '0' and '1'
- 0 ≤ m, n ≤ 100
Hints:
Each string is an item that costs (zeros, ones) and is worth exactly 1 point. Choosing items under a budget so the total worth is maximized — which classic problem is that?
It is 0/1 knapsack, just with a two-dimensional capacity. Let dp[i][j] be the most strings you can pick using at most i zeros and j ones, and fold the strings in one at a time, sweeping both budgets downward so no string is counted twice.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
Expected output: 4