Algorithm
Problem Name: 474. 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 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.
Constraints:
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i]consists only of digits'0'and'1'.1 <= m, n <= 100
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (String s : strs) {
int[] count = getCountForZeroAndOne(s);
for (int zeroes = m; zeroes >= count[0]; zeroes--) {
for (int ones = n; ones >= count[1]; ones--) {
dp[zeroes][ones] = Math.max(1 + dp[zeroes - count[0]][ones - count[1]], dp[zeroes][ones]);
}
}
}
return dp[m][n];
}
private int[] getCountForZeroAndOne(String s) {
int[] count = {0, 0};
for (char c : s.toCharArray()) {
if (c == '0') {
count[0]++;
} else {
count[1]++;
}
}
return count;
}
}
Input
strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output
4
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const findMaxForm = function(strs, m, n) {
const memo = Array.from(new Array(m + 1), () => new Array(n + 1).fill(0))
let numZeroes
let numOnes
for (let s of strs) {
numZeroes = numOnes = 0
for (let c of s) {
if (c === '0') numZeroes++
else if (c === '1') numOnes++
}
for (let i = m; i >= numZeroes; i--) {
for (let j = n; j >= numOnes; j--) {
memo[i][j] = Math.max(memo[i][j], memo[i - numZeroes][j - numOnes] + 1)
}
}
}
return memo[m][n]
}
Input
strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output
4
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findMaxForm(self, strs, m, n):
res = [0]
memo = set()
def dfs(st, zeros, ones, cnt):
if (zeros, ones, cnt) not in memo:
if cnt > res[0]:
res[0] = cnt
if zeros or ones:
for s in st:
if st[s] and cntr[s]["0"] <= zeros and cntr[s]["1"] <= ones:
st[s] -= 1
dfs(st, zeros - cntr[s]["0"], ones - cntr[s]["1"], cnt + 1)
st[s] += 1
memo.add((zeros, ones, cnt))
cntr = {s:collections.Counter(s) for s in strs}
dfs(collections.Counter(strs), m, n, 0)
return res[0]
Input
strs = ["10","0","1"], m = 1, n = 1
Output
2