Solution: Ones and Zeroes
Tags: algorithms, javascript, java, python
Published: 2021-04-02 11:15:24

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/ones-and-zeroes/discuss/1138695).*

---

#### [Leetcode Problem #474 (*Medium*): Ones and Zeroes](https://leetcode.com/problems/ones-and-zeroes/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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.<br>Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.<br>{"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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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];
    }
};
```