## 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 <= 600`
• `1 <= strs[i].length <= 100`
• `strs[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; zeroes--) {
for (int ones = n; ones >= count; ones--) {
dp[zeroes][ones] = Math.max(1 + dp[zeroes - count][ones - count], 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++;
} else {
count++;
}
}
return count;
}
}
``````
Copy The Code &

Input

cmd
strs = ["10","0001","111001","1","0"], m = 5, n = 3

Output

cmd
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]
}
``````
Copy The Code &

Input

cmd
strs = ["10","0001","111001","1","0"], m = 5, n = 3

Output

cmd
4

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findMaxForm(self, strs, m, n):
res = 
memo = set()
def dfs(st, zeros, ones, cnt):
if (zeros, ones, cnt) not in memo:
if cnt > res:
res = 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

cntr = {s:collections.Counter(s) for s in strs}
dfs(collections.Counter(strs), m, n, 0)
return res
``````
Copy The Code &

Input

cmd
strs = ["10","0","1"], m = 1, n = 1

Output

cmd
2