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 a set y if all elements of x are also elements of y.
Example 1:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
Example 2:
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.
This problem is a typical 0-1 knapsack problem, we need to pick several strings in provided strings to get the maximum number of strings using limited number 0 and 1. We can create a three dimensional array, in which dp[i][j][k] means the maximum number of strings we can get from the first i argument strs using limited j number of '0's and k number of '1's.
For dp[i][j][k], we can get it by fetching the current string i or discarding the current string, which would result in dp[i][j][k] = dp[i-1][j-numOfZero(strs[i])][i-numOfOnes(strs[i])] and dp[i][j][k] = dp[i-1][j][k]; We only need to treat the larger one in it as the largest number for dp[i][j][k].
public int findMaxForm(String[] strs, int m, int n) {
int l = strs.length;
int[][][] dp = new int[l+1][m+1][n+1];
for (int i = 0; i < l+1; i++) {
int[] nums = new int[]{0,0};
if (i > 0) {
nums = calculate(strs[i-1]);
}
for (int j = 0; j < m+1; j++) {
for (int k = 0; k < n+1; k++) {
if (i == 0) {
dp[i][j][k] = 0;
} else if (j>=nums[0] && k>=nums[1]) {
dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-nums[0]][k-nums[1]]+1);
} else {
dp[i][j][k] = dp[i-1][j][k];
}
}
}
}
return dp[l][m][n];
}
private int[] calculate(String str) {
int[] res = new int[2];
Arrays.fill(res, 0);
for (char ch : str.toCharArray()) {
if (ch == '0') {
res[0]++;
} else if (ch == '1') {
res[1]++;
}
}
return res;
}