> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/ones-and-zeroes.md).

# Ones and Zeroes

Given an array, `strs`, with strings consisting of only `0s` and `1s`. Also two integers `m` and `n`.

Now your task is to find the maximum number of strings that you can form with given **m** `0s` and **n** `1s`. Each `0` and `1` can be used at most **once**.

**Example 1:**

```
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are "10","0001","1","0".
```

**Example 2:**

```
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".
```

**Constraints:**

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

```java
/*
The problem can be interpreted as: What's the max number of str can we pick from strs with limitation of m "0"s and n "1"s.
Thus we can define dp[i][j] stands for max number of str can we pick from strs with limitation of i "0"s and j "1"s.
For each str, assume it has a "0"s and b "1"s, we update the dp array iteratively and set dp[i][j] = Math.max(dp[i][j], dp[i - a][j - b] + 1). So at the end, dp[m][n] is the answer.
*/

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] list = new int[strs.length][];
        int index = 0;
        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray())
                if (c == '0')
                    zeros++;
                else
                    ones++;
            list[index++] = new int[] { zeros, ones };
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int[] x : list) {
            for (int i = m; i - x[0] >= 0; i--)
                for (int j = n; j - x[1] >= 0; j--)
                    dp[i][j] = Math.max(1 + dp[i - x[0]][j - x[1]], dp[i][j]);
        }
        return dp[m][n];
    }
}
```