# 474     Ones and Zeroes

## 474. [Ones and Zeroes](https://leetcode.com/problems/ones-and-zeroes/description/)

## 1. Question

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of **m**`0s`and **n**`1s`respectively. On the other hand, there is an array with strings consisting of only`0s`and`1s`.

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

**Note:**

1. The given numbers of`0s`and`1s`will both not exceed`100`
2. The size of given string array won't exceed`600`.

**Example 1:**

```
Input: Array = {"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: Array = {"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".
```

## 2. Implementation

**(1) DP**

思路: 这题要我们用m个0和n个1，组成最多的string(每个string都由0或1组成)。这是很明显的0-1背包问题，是二维的0-1背包问题，可以直接用模板写

```java
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0 || m < 0 || n < 0) {
            return 0;
        }

        // dp[i][j][k] means the max number of strings we can form with number of j 0s and k 1s for the first i strings in strs
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        int[] count = new int[2];

        for (int i = 0; i <= strs.length; i++) {
            // The first row is empty string, skip the first row
            if (i == 0) continue;

            count = countOnesAndZeroes(strs[i - 1]);

            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    // When we have enough 1s and 0s to form the current string string strs[i - 1]
                    // Two strategies: Form it or skip it
                    if (count[0] <= j && count[1] <= k) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - count[0]][k - count[1]] + 1);
                    }
                    // Do nothing
                    else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

    public int[] countOnesAndZeroes(String s) {
        int[] count = new int[2];

        for (char c : s.toCharArray()) {
            ++count[c - '0'];
        }
        return count;
    }
}
```

**(2) DP空间优化**

```java
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0|| m < 0 || n < 0) {
            return 0;
        }

        int[][] dp = new int[m + 1][n + 1];
        int[] count = new int[2];

        for (int i = 0; i < strs.length; i++) {
            count = countOnesAndZeroes(strs[i]);

            for (int j = m; j >= count[0]; j--) {
                for (int k = n; k >= count[1]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - count[0]][k - count[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public int[] countOnesAndZeroes(String s) {
        int[] count = new int[2];

        for (char c :s.toCharArray()) {
            ++count[c - '0'];
        }
        return count;
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(k \* l \* m \* n), 空间复杂度O(kmn)

**DP空间优化:** 时间复杂度O(k \* l \* m \* n), 空间复杂度O(mn)