## DEV Community is a community of 674,199 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Solution: Ones and Zeroes

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.

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.

#### 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 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`.

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

• `1 <= strs.length <= 600`
• `1 <= strs[i].length <= 100`
• `strs[i]` consists only of digits `'0'` and `'1'`.
• `1 <= m, n <= 100`

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

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:

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

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

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

``````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];
}
};
``````