Ones and Zeroes
Medium · Dynamic Programming · Array · String · Dynamic Programming
Problem
You are given an array strs of binary strings and two integers m and n.
Choose a subset of the strings such that, across all chosen strings together, there are at most m zeros and at most n ones. Return the largest possible size of such a subset.
Examples
Input: strs = ["01","110","0","1000","11"], m = 3, n = 2 Output: 2
For example {"01", "0"} or {"0", "11"} fits; no three strings stay within 3 zeros and 2 ones.
Input: strs = ["1","1","0","00"], m = 1, n = 2 Output: 3
Take "1", "1" and "0": exactly 1 zero and 2 ones.
Input: strs = ["000","111"], m = 2, n = 2 Output: 0
Each string alone needs three of one digit, so the best subset is empty.
Constraints
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] contains only '0' and '1'
- 1 <= m, n <= 100
Approaches
- Baseline: try every subset — time O(2^L · L), space O(L)
Follow-up
Every extra resource adds one dimension to the knapsack table. The use cases give each string a value (maximize total value instead of count) and ask how many subsets fit, which swaps max for a sum.
Related problems
Start free on Cariara · Coding problems · System design studio
