DSA problem
Ones and Zeroes
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 0's and n 1's in the subset. A set x is a subset of y if every element of x is also in y.
This is a two-dimensional 0/1 knapsack problem. Each binary string is an item with two capacity costs: the number of zeros it contains and the number of ones it contains. The "value" of each item is 1 (it contributes one string to the subset), and we want to maximize total value subject to two simultaneous capacity constraints (at most m zeros and at most n ones in total).
A 3D DP dp[i][j][k] where i indexes the string, j is zeros used, and k is ones used would work in O(L * m * n) time and space, but we can compress to a 2D rolling array dp[j][k] exactly like the 1D rolling trick on standard knapsack — process strings one at a time and iterate both capacity dimensions from high to low.
The optimal solution precomputes (zeros, ones) for each string in O(L) time, then for each string updates dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1) for j from m down to zeros and k from n down to ones. The high-to-low iteration ensures each string is considered at most once per state, giving O(L * m * n) total time and O(m * n) extra space.
Examples
strs = ["10","0001","111001","1","0"], m = 5, n = 34strs = ["10","0","1"], m = 1, n = 12strs = ["111","1000","1000","1000"], m = 9, n = 33Constraints
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] consists only of digits 0 and 1.
- 1 <= m, n <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.