*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #474 (*Medium*): Ones and Zeroes

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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 areat most`m`

`0`

's and`n`

`1`

's in the subset.A set

`x`

is asubsetof a set`y`

if all elements of`x`

are also elements of`y`

.

####
*Examples:*

*Examples:*

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:*

*Constraints:*

`1 <= strs.length <= 600`

`1 <= strs[i].length <= 100`

`strs[i]`

consists only of digits`'0'`

and`'1'`

.`1 <= m, n <= 100`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

This problem is a variation on the **0-1 Knapsack Problem** with a wrinkle: each item has a 2-dimensional weight, but a constant value. If we were to naively attempt every single permutation of up to **600** strings, that would be **2^600** permutations.

But thankfully we're not tasked with keeping track of each permutation, but simply the maximum number of items. This calls for the use of **dynamic programming** (**DP**) to reduce the overall complexity by instead only keeping track of the best results of the various subproblems encountered while working our way to the eventual answer.

For our DP array (**dp**), **dp[i][j]** will represent the largest number of items that can be added to yield **i** zeros and **j** ones. Thus, our answer will ultimately be **dp[M][N]**. We'll naturally being doing a bottom-up DP approach, as we'll be starting with no data and iterating through the input array (**S**), adding more data to **dp** as we go.

Since each string in **S** will require us to iterate through the entirety of **dp** looking for data to update, we'll need to do this iteration in a top-down fashion, to avoid interfering with our overall bottom-up approach, which would occur if we were to update entries that will be the basis for later updates in the same pass.

Once we reach the end, we return **dp[M][N]**.

####
*Implementation:*

*Implementation:*

As each entry in dp will be in the range **[0,200]** based on the constraints for **M** and **N**, we have the option of using an **8-bit** number storage array for the purpose.

Python has other, faster solutions, but this is one of the easiest, and mirrors the solutions in the other languages.

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var findMaxForm = function(S, M, N) {
let dp = Array.from({length:M+1},() => new Uint8Array(N+1))
for (let i = 0; i < S.length; i++) {
let str = S[i], zeros = 0, ones = 0
for (let j = 0; j < str.length; j++)
str.charAt(j) === "0" ? zeros++ : ones++
for (let j = M; j >= zeros; j--)
for (let k = N; k >= ones; k--)
dp[j][k] = Math.max(dp[j][k], dp[j-zeros][k-ones] + 1)
}
return dp[M][N]
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def findMaxForm(self, S: List[str], M: int, N: int) -> int:
dp = [[0 for _ in range(N+1)] for _ in range(M+1)]
for str in S:
zeros = str.count("0")
ones = len(str) - 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]
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int findMaxForm(String[] S, int M, int N) {
int[][] dp = new int[M+1][N+1];
for (String str : S) {
int zeros = 0, ones = 0;
for (char c : str.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];
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
int findMaxForm(vector<string>& S, int M, int N) {
int dp[101][101]{0};
for (string str : S) {
int zeros = 0, ones = 0;
for (char c : str)
c == '0' ? zeros++ : ones++;
for (int i = M; i >= zeros; i--)
for (int j = N; j >= ones; j--)
dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones] + 1);
}
return dp[M][N];
}
};
```

## Top comments (0)