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:
1
2
3
4
5
Input:
strs = ["10","0","1"], m = 1, n = 1
Output:
2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.
Use dynamic programming to select the largest subset of strings such that the total number of 0’s and 1’s does not exceed m and n, similar to the 2D knapsack problem.
classSolution {
publicintfindMaxForm(String[] strs, int m, int n) {
int[][] dp =newint[m+1][n+1];
for (String s : strs) {
int zeros = 0, ones = 0;
for (char c : s.toCharArray()) {
if (c =='0') zeros++;
else ones++;
}
for (int i = m; i >= zeros; --i) {
for (int j = n; j >= ones; --j) {
dp[i][j]= Math.max(dp[i][j], dp[i-zeros][j-ones]+1);
}
}
}
return dp[m][n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
funfindMaxForm(strs: Array<String>, m: Int, n: Int): Int {
val dp = Array(m+1) { IntArray(n+1) }
for (s in strs) {
val zeros = s.count { it=='0' }
val ones = s.length - zeros
for (i in m downTo zeros) {
for (j in n downTo ones) {
dp[i][j] = maxOf(dp[i][j], dp[i-zeros][j-ones]+1)
}
}
}
return dp[m][n]
}
}
1
2
3
4
5
6
7
8
9
10
classSolution:
deffindMaxForm(self, strs: list[str], m: int, n: int) -> int:
dp = [[0]*(n+1) for _ in range(m+1)]
for s in strs:
zeros = s.count('0')
ones = len(s) - zeros
for i in range(m, zeros-1, -1):
for j in range(n, ones-1, -1):
dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
return dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
pubfnfind_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
let m = m asusize;
let n = n asusize;
letmut dp =vec![vec![0; n+1]; m+1];
for s in strs.iter() {
let zeros = s.chars().filter(|&c| c =='0').count();
let ones = s.len() - zeros;
for i in (zeros..=m).rev() {
for j in (ones..=n).rev() {
dp[i][j] = dp[i][j].max(dp[i-zeros][j-ones]+1);
}
}
}
dp[m][n]
}
}