# LeetCode 474: Ones and Zeroes

## Problem Restatement

We are given an array of binary strings:

```python
strs
```

We are also given two integers:

```python
m
n
```

We can choose some strings from `strs`.

The chosen strings must use at most:

```python
m zeros
n ones
```

Each string can be chosen at most once.

We need to return the largest possible number of strings we can choose. The official problem asks for the size of the largest subset of `strs` with at most `m` zeroes and `n` ones.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `strs`, an array of binary strings |
| Input | `m`, maximum number of `0` characters |
| Input | `n`, maximum number of `1` characters |
| Output | Maximum number of strings we can choose |
| Rule | Each string can be used at most once |

Function shape:

```python
def findMaxForm(strs: list[str], m: int, n: int) -> int:
    ...
```

## Examples

Example 1:

```python
strs = ["10", "0001", "111001", "1", "0"]
m = 5
n = 3
```

One valid choice is:

```python
"10", "0001", "1", "0"
```

Zero count:

```python
"10"   -> 1 zero
"0001" -> 3 zeros
"1"    -> 0 zeros
"0"    -> 1 zero

total zeros = 5
```

One count:

```python
"10"   -> 1 one
"0001" -> 1 one
"1"    -> 1 one
"0"    -> 0 ones

total ones = 3
```

We chose `4` strings.

Answer:

```python
4
```

Example 2:

```python
strs = ["10", "0", "1"]
m = 1
n = 1
```

We could choose `"10"` alone.

But a better choice is:

```python
"0", "1"
```

This uses one zero and one one, and chooses two strings.

Answer:

```python
2
```

## First Thought: Try Every Subset

A direct idea is to generate every subset of `strs`.

For each subset:

1. Count all zeros.
2. Count all ones.
3. If both counts fit within `m` and `n`, update the best subset size.

This is correct, but it is too slow.

If there are `k` strings, then there are:

```python
2^k
```

subsets.

Since the number of strings can be large, brute force is not practical. The older statement lists up to `600` strings and both `m` and `n` up to `100`.

## Key Insight

This is a 0/1 knapsack problem with two resource limits.

Each string is an item.

Its cost is:

```python
number of zeros
number of ones
```

Its value is:

```python
1
```

because choosing one string increases the subset size by one.

We need the maximum total value while staying within two budgets: zeros and ones.

So we use dynamic programming.

Let:

```python
dp[i][j]
```

mean:

```python
the maximum number of strings we can choose using at most i zeros and j ones
```

## Algorithm

Create a 2D DP table:

```python
dp = [[0] * (n + 1) for _ in range(m + 1)]
```

For each string `s`:

1. Count its zeros and ones.
2. Update the DP table in reverse order.
3. For each possible zero budget `i` and one budget `j`, decide whether taking this string improves the answer.

The transition is:

```python
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
```

We iterate backward so each string is used at most once.

## Why Reverse Order Matters

Suppose we update `dp` from small budgets to large budgets.

Then after using the current string once, the updated value could be used again in the same iteration.

That would allow one string to be chosen multiple times.

But this is a 0/1 problem: each string can be used at most once.

So we update backward:

```python
for i in range(m, zeros - 1, -1):
    for j in range(n, ones - 1, -1):
        ...
```

This ensures that when we compute `dp[i][j]`, the previous state:

```python
dp[i - zeros][j - ones]
```

still comes from before considering the current string.

## Walkthrough

Use:

```python
strs = ["10", "0", "1"]
m = 1
n = 1
```

Start:

```python
dp = [
    [0, 0],
    [0, 0],
]
```

Process `"10"`.

It has:

```python
zeros = 1
ones = 1
```

So:

```python
dp[1][1] = 1
```

Process `"0"`.

It has:

```python
zeros = 1
ones = 0
```

Update:

```python
dp[1][0] = 1
dp[1][1] = max(1, dp[0][1] + 1) = 1
```

Process `"1"`.

It has:

```python
zeros = 0
ones = 1
```

Update:

```python
dp[0][1] = 1
dp[1][1] = max(1, dp[1][0] + 1) = 2
```

The final answer is:

```python
dp[1][1] = 2
```

## Correctness

The DP state `dp[i][j]` stores the maximum number of strings that can be selected using at most `i` zeros and `j` ones among the strings already processed.

For a new string with `zeros` zeros and `ones` ones, there are two choices.

We can skip it, leaving `dp[i][j]` unchanged.

Or, if `i >= zeros` and `j >= ones`, we can take it. Then the remaining budget before taking it is:

```python
i - zeros
j - ones
```

The best subset for that remaining budget has size:

```python
dp[i - zeros][j - ones]
```

Taking the current string adds one more selected string.

The transition takes the better of these two choices.

Because we process every string once and update budgets backward, no string can be used more than once.

Therefore, after all strings are processed, `dp[m][n]` is the maximum subset size that satisfies the zero and one limits.

## Complexity

Let:

```python
k = len(strs)
L = maximum length of a string
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(k * (L + m * n))` | Count each string, then update the DP table |
| Space | `O(m * n)` | The DP table has `(m + 1) * (n + 1)` cells |

## Implementation

```python
class Solution:
    def findMaxForm(self, strs: list[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for s in strs:
            zeros = s.count("0")
            ones = len(s) - 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]
```

## Code Explanation

We create the DP table:

```python
dp = [[0] * (n + 1) for _ in range(m + 1)]
```

The row index is the zero budget.

The column index is the one budget.

For each string, we count zeros:

```python
zeros = s.count("0")
```

Since the string is binary, the number of ones is:

```python
ones = len(s) - zeros
```

Then we update budgets backward:

```python
for i in range(m, zeros - 1, -1):
    for j in range(n, ones - 1, -1):
```

The update means:

```python
take this string if it improves the best answer for this budget
```

Finally:

```python
return dp[m][n]
```

returns the largest subset size under the full budget.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findMaxForm(
        ["10", "0001", "111001", "1", "0"],
        5,
        3,
    ) == 4

    assert s.findMaxForm(
        ["10", "0", "1"],
        1,
        1,
    ) == 2

    assert s.findMaxForm(
        ["0", "0", "1", "1"],
        2,
        2,
    ) == 4

    assert s.findMaxForm(
        ["00", "000"],
        1,
        10,
    ) == 0

    assert s.findMaxForm(
        ["1", "11", "111"],
        0,
        3,
    ) == 2

    assert s.findMaxForm(
        [],
        5,
        5,
    ) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Confirms expected answer `4` |
| `["10","0","1"]` | Choosing two smaller strings beats one larger string |
| Repeated simple strings | Uses both budgets fully |
| Only zero-heavy strings | Cannot choose any if zero budget is too small |
| Only one-heavy strings | Zero budget can be `0` |
| Empty input | No strings can be chosen |