# Leetcode 474. Ones and Zeroes

[link](https://leetcode.com/problems/ones-and-zeroes)

---

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

---

Initialize a dictionary dp to store previously computed results. The key (i, m, n) represents the current index in the strs list, the remaining count of '0's (m), and the remaining count of '1's (n), and the value is the maximum number of binary strings that can be formed from the current index.

Define a recursive function dfs(i, m, n) that explores all possible combinations of choosing or not choosing strings from the strs list starting from the i-th index while considering the remaining counts of '0's and '1's.

In the recursive function:

1. If i is equal to the length of strs, return 0 because there are no more strings to consider.
2. Check if the result for the current (i, m, n) triplet is already computed in the dp dictionary. If it is, return the cached result.
3. Calculate the number of '0's and '1's in the current string strs[i] using the count method.
4. Initialize dp[(i, m, n)] with the result of the recursive call dfs(i + 1, m, n) (i.e., not choosing the current string).
5. Check if it's possible to choose the current string by ensuring that the counts of '0's (mCnt) and '1's (nCnt) in the string do not exceed the remaining counts m and n. If the conditions are met, update dp[(i, m, n)] to be the maximum between the current value and 1 + dfs(i + 1, m - mCnt, n - nCnt) (i.e., choosing the current string and updating the remaining counts).
6. Return dp[(i, m, n)] as the maximum number of binary strings that can be formed from the current index.
7.
Finally, return the result of calling dfs(0, m, n) as the answer, which represents the maximum number of binary strings that can be formed while satisfying the constraints.

#### Solution 1

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = {}

        def dfs(i, m, n):
            if i == len(strs):
                return 0
            
            if (i, m, n) in dp:
                return dp[(i, m, n)]

            mCnt, nCnt = strs[i].count("0"), strs[i].count("1")
            dp[(i, m, n)] = dfs(i + 1, m, n)

            if mCnt <= m and nCnt <= n:
                dp[(i, m, n)] = max(dp[(i, m, n)], 1 + dfs(i + 1, m - mCnt, n - nCnt))

            return dp[(i, m, n)]
 
        return dfs(0, m, n)
        

O(T): O(n * m * i)
O(S): O(n)