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 0s and n 1s in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
Examples
Input: [["10","0001","111001","1","0"],5,3]
Output: 4
Input: [["10","0","1"],1,1]
Output: 2
Hints
For each string in `strs`, count the number of `0`s and `1`s it contains. This will help you determine the "weight" of each item in the knapsack problem.
Iterate through each string and update the DP table in reverse order (from `m` to `0`s and `n` to `0`s) to avoid reusing the same string multiple times in the subset.
For each string, if including it improves the subset size (i.e., `dp[i - zeros][j - ones] + 1 > dp[i][j]`), update the DP table accordingly. The final answer will be `dp[m][n]`.
Related Problems
Ones and Zeroes
You are given an array of binary strings `strs` and two integers `m` and `n`.