# Ones and Zeroes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/ones-and-zeroes)
Canonical: https://scaleengineer.com/dsa/problems/ones-and-zeroes
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, String
---
## Problem
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`.

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

# Approaches
## Brute Force with Recursion
This approach explores all possible subsets of the given strings. For each string, we have two choices: either include it in our subset or not. This naturally leads to a recursive solution. We define a recursive function that tries both possibilities at each step, effectively traversing a binary decision tree.
**Time:** O(2^L * S), where L is the length of `strs` and S is the maximum length of a string. For each of the `2^L` recursive paths, we may perform a count operation taking O(S) time. This is prohibitively slow for the given constraints. · **Space:** O(L), where L is the length of `strs`. This space is used by the recursion stack.
**Pros:** Simple to understand and implement.; Follows a natural, straightforward logic.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.; Redundantly computes solutions for the same subproblems multiple times.
### Explanation
The core idea is to generate every single subset of `strs`. A recursive function, say `calculate(strs, index, zeros, ones)`, is defined. This function calculates the size of the largest subset from the subarray `strs[index:]` given the remaining capacity of `zeros` and `ones`.

In each call, for the string at `strs[index]`, we have two choices:
1.  **Exclude `strs[index]`**: We move to the next string without changing the `zeros` and `ones` count. The result is `calculate(strs, index + 1, zeros, ones)`.
2.  **Include `strs[index]`**: First, we count the zeros and ones in `strs[index]`. If we have enough capacity (i.e., `zeros >= count_zero` and `ones >= count_one`), we include it. The result is `1 + calculate(strs, index + 1, zeros - count_zero, ones - count_one)`.

The function returns the maximum of the results from these two choices. The base case for the recursion is when `index` reaches the end of the `strs` array, in which case we return 0 as no more strings can be added. The initial call would be `calculate(strs, 0, m, n)`. This method explores the entire decision tree, which has `2^L` leaves, where `L` is the number of strings.

```java
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        return calculate(strs, 0, m, n);
    }

    private int calculate(String[] strs, int i, int zeros, int ones) {
        if (i == strs.length) {
            return 0;
        }

        // Calculate cost of current string
        int[] count = countZerosOnes(strs[i]);
        int zerosInStr = count[0];
        int onesInStr = count[1];

        // Option 1: Exclude strs[i]
        int res = calculate(strs, i + 1, zeros, ones);

        // Option 2: Include strs[i] if possible
        if (zeros >= zerosInStr && ones >= onesInStr) {
            res = Math.max(res, 1 + calculate(strs, i + 1, zeros - zerosInStr, ones - onesInStr));
        }

        return res;
    }

    private int[] countZerosOnes(String s) {
        int[] count = new int[2];
        for (char c : s.toCharArray()) {
            if (c == '0') {
                count[0]++;
            } else {
                count[1]++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Define a recursive function, say `calculate(strs, index, zeros, ones)`, which computes the size of the largest subset from the subarray `strs[index:]` given the remaining capacity of `zeros` and `ones`.
- For each string at `strs[index]`, there are two choices:
  1.  **Exclude `strs[index]`**: Recursively call `calculate(strs, index + 1, zeros, ones)`.
  2.  **Include `strs[index]`**: If there's enough capacity (i.e., `zeros >= count_zero` and `ones >= count_one`), recursively call `1 + calculate(strs, index + 1, zeros - count_zero, ones - count_one)`.
- The function returns the maximum value obtained from these two choices.
- The base case for the recursion is when `index` reaches the end of the `strs` array, at which point it returns 0.
- The initial call to start the process is `calculate(strs, 0, m, n)`.

## Memoized Recursion (Top-Down DP)
The brute-force recursive approach suffers from re-calculating the same subproblems multiple times. A subproblem can be uniquely identified by the current index `i` in the `strs` array, the remaining zeros `m`, and the remaining ones `n`. We can optimize this by storing the results of these subproblems in a memoization table (a 3D array) and reusing them when needed. This technique is known as top-down dynamic programming.
**Time:** O(L * m * n + L * S). The number of states is `L * m * n`, and each state is computed once. The computation for each state involves counting zeros and ones, which takes O(S). We can optimize this by pre-calculating the counts, making the DP part O(L * m * n). · **Space:** O(L * m * n), where L is the length of `strs`. This space is dominated by the 3D memoization table.
**Pros:** Significantly more efficient than brute force and guaranteed to pass within the time limits.; The logic closely follows the recursive structure, making it relatively easy to transition from the brute-force solution.
**Cons:** Requires a large amount of memory for the 3D memoization table, which can be a concern for larger constraints.; Still has the overhead associated with recursion, although much less than the brute-force approach.
### Explanation
We augment the recursive solution with a 3D array, `memo[L][m+1][n+1]`, to store the results of computed subproblems, where `L` is the length of `strs`. The state `memo[i][j][k]` will store the result of `calculate(strs, i, j, k)`, which is the maximum subset size from `strs[i:]` with `j` zeros and `k` ones remaining.

Before computing the result for a state `(i, j, k)`, we first check if `memo[i][j][k]` has already been computed. If so, we return the stored value immediately. If not, we compute it using the same recursive logic as the brute-force approach: considering both including and excluding the current string `strs[i]`. After computing the result, we store it in `memo[i][j][k]` before returning it. This ensures that each subproblem `(i, j, k)` is solved only once.

```java
class Solution {
    private Integer[][][] memo;

    public int findMaxForm(String[] strs, int m, int n) {
        memo = new Integer[strs.length][m + 1][n + 1];
        return calculate(strs, 0, m, n);
    }

    private int calculate(String[] strs, int i, int zeros, int ones) {
        if (i == strs.length) {
            return 0;
        }
        if (memo[i][zeros][ones] != null) {
            return memo[i][zeros][ones];
        }

        int[] count = countZerosOnes(strs[i]);
        int zerosInStr = count[0];
        int onesInStr = count[1];

        // Option 1: Exclude strs[i]
        int res = calculate(strs, i + 1, zeros, ones);

        // Option 2: Include strs[i] if possible
        if (zeros >= zerosInStr && ones >= onesInStr) {
            res = Math.max(res, 1 + calculate(strs, i + 1, zeros - zerosInStr, ones - onesInStr));
        }

        memo[i][zeros][ones] = res;
        return res;
    }

    private int[] countZerosOnes(String s) {
        int[] count = new int[2];
        for (char c : s.toCharArray()) {
            if (c == '0') {
                count[0]++;
            } else {
                count[1]++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a 3D array `memo[strs.length][m+1][n+1]` with a sentinel value (e.g., `null` or -1) to indicate that a state has not been computed.
- Define a recursive helper function `calculate(strs, index, zeros, ones, memo)`.
- In the helper function, first check the base case: if `index == strs.length`, return 0.
- Before any computation, check if `memo[index][zeros][ones]` already holds a computed value. If so, return it immediately.
- If not, perform the same logic as the brute-force approach: compute the result by taking the maximum of including and excluding the current string `strs[index]`.
- Store the computed result in `memo[index][zeros][ones]` before returning it.
- The initial call is `findMaxForm(strs, m, n)` which sets up the memoization table and calls the helper function.

## Iterative Dynamic Programming (Bottom-Up)
This problem is a variation of the 0/1 Knapsack problem, but with two constraints (number of zeros and ones) instead of one (weight). We can solve it using bottom-up dynamic programming. We build a DP table that stores the solution for subproblems and iterate through the strings, updating the table at each step. This approach avoids recursion and often has better space complexity.
**Time:** O(L * m * n + L * S). The outer loop runs L times. The two inner loops run m and n times. Counting zeros and ones for each string takes O(S). The total time is dominated by the three nested loops. · **Space:** O(m * n) for the 2D DP table. This is a significant improvement over the memoized recursion approach.
**Pros:** Most efficient in terms of space complexity.; Avoids recursion overhead, which can lead to slightly better performance in practice.; It's a classic and powerful DP pattern applicable to many similar problems.
**Cons:** Can be slightly less intuitive to formulate than the top-down recursive approach for beginners.
### Explanation
We define a 2D DP table, `dp[i][j]`, which represents the size of the largest subset that can be formed using at most `i` zeros and `j` ones. The table size will be `(m+1) x (n+1)`. We initialize the `dp` table with all zeros, as an empty set is always a valid subset of size 0.

We iterate through each string `s` in the input array `strs`. For each string, we determine its "cost" in terms of zeros (`num_zeros`) and ones (`num_ones`). Then, we update the `dp` table. For each cell `dp[i][j]`, we consider whether to include the current string `s`. The new value for `dp[i][j]` will be the maximum of:
1.  Its current value (not including `s`).
2.  `1 + dp[i - num_zeros][j - num_ones]` (including `s`, if we have enough capacity, i.e., `i >= num_zeros` and `j >= num_ones`).

To ensure that each string is considered at most once (the 0/1 property), we must iterate the loops for `i` and `j` backwards, from `m` down to `num_zeros` and `n` down to `num_ones`, respectively. This prevents using the information of the current string `s` multiple times in the same update step. After iterating through all the strings, the value at `dp[m][n]` will be the final answer.

```java
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (String s : strs) {
            int zeros = 0;
            int ones = 0;
            for (char c : s.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], 1 + dp[i - zeros][j - ones]);
                }
            }
        }
        return dp[m][n];
    }
}
```
### Algorithm
- Create a 2D array `dp[m+1][n+1]` and initialize all its elements to 0.
- For each string `s` in the input array `strs`:
  - Count the number of zeros (`num_zeros`) and ones (`num_ones`) in `s`.
  - Iterate backwards through the DP table to update its values. For `i` from `m` down to `num_zeros`:
    - For `j` from `n` down to `num_ones`:
      - Update `dp[i][j]` with the maximum of its current value and `1 + dp[i - num_zeros][j - num_ones]`.
- After iterating through all the strings, the value at `dp[m][n]` is the final answer.

# Solutions
### Java

```java
class Solution { public int findMaxForm ( String [] strs , int m , int n ) { int [][] f = new int [ m + 1 ][ n + 1 ]; for ( String s : strs ) { int [] cnt = count ( s ); for ( int i = m ; i >= cnt [ 0 ]; -- i ) { for ( int j = n ; j >= cnt [ 1 ]; -- j ) { f [ i ][ j ] = Math . max ( f [ i ][ j ], f [ i - cnt [ 0 ]][ j - cnt [ 1 ]] + 1 ); } } } return f [ m ][ n ]; } private int [] count ( String s ) { int [] cnt = new int [ 2 ]; for ( int i = 0 ; i < s . length (); ++ i ) { ++ cnt [ s . charAt ( i ) - '0' ]; } return cnt ; } }
```

### CPP

```cpp
class Solution { public: int findMaxForm ( vector < string >& strs , int m , int n ) { int f [ m + 1 ][ n + 1 ]; memset ( f , 0 , sizeof ( f )); for ( auto & s : strs ) { auto [ a , b ] = count ( s ); for ( int i = m ; i >= a ; -- i ) { for ( int j = n ; j >= b ; -- j ) { f [ i ][ j ] = max ( f [ i ][ j ], f [ i - a ][ j - b ] + 1 ); } } } return f [ m ][ n ]; } pair < int , int > count ( string & s ) { int a = count_if ( s . begin (), s . end (), []( char c ) { return c == '0' ; }); return { a , s . size () - a }; } };
```

### Python

```python
class Solution : def findMaxForm ( self , strs : List [ str ], m : int , n : int ) -> int : f = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] for s in strs : a , b = s . count ( "0" ), s . count ( "1" ) for i in range ( m , a - 1 , - 1 ): for j in range ( n , b - 1 , - 1 ): f [ i ][ j ] = max ( f [ i ][ j ], f [ i - a ][ j - b ] + 1 ) return f [ m ][ n ]
```