# Ones and Zeroes (Medium) 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:** ```plaintext 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:** ```plaintext Input: strs = ["10","0","1"], m = 1, n = 1 Output: 2 Explanation: The largest subset is {"0", "1"}, so the answer is 2. ``` **1️⃣ Explanation of the Problem in Simple Terms** You’re given: * An array of binary strings, for example `["10", "0001", "111001", ...]`. * Two integers, `m` and `n`. You can use **at most** `m` zeroes and `n` ones **in total** to “form” some subset of these strings. Forming a string means you allocate as many 0’s and 1’s as appear in that string from your budget of `m` zeroes and `n` ones. **Each string can be used at most once**. Your goal is to **maximize the number of strings** you can form without exceeding `m` total zeroes or `n` total ones. * If a string has `x` zeroes and `y` ones, then choosing this string consumes `x` of your available zeroes (out of `m`) and `y` of your available ones (out of `n`). * You want to find the *largest* subset of the given strings that can be chosen without exceeding these budgets. --- **2️⃣ Decision Tree (Naive Recursive Visualization)** Let’s look at a small example: ```plaintext strings = ["10", "00", "1"] m = 2, n = 2 ``` * Count zeroes and ones in each string: * "10" -> 1 zero, 1 one * "00" -> 2 zeroes, 0 ones * "1" -> 0 zeroes, 1 one A naive recursive approach would define something like `dfs(index, zerosUsed, onesUsed)`, which returns the maximum number of strings you can form starting from `index` given you’ve already used some zeroes/ones out of `m` and `n`. At each `index`, you can: * **Skip** the current string → no consumption of zeroes/ones, move to next string. * **Pick** the current string (if possible) → reduce the available zeroes/ones, move to next string. The tree might look like (showing only the top level decisions to illustrate the exponential branching): ```plaintext dfs(0, m=2, n=2) / \ Pick "10" Skip "10" / \ dfs(1, m=1, n=1) dfs(1, m=2, n=2) / \ / \ Pick "00" Skip "00" Pick "00" Skip "00" ... ... ... ... ``` This quickly becomes exponential as you recurse further. We will optimize via memoization or tabulation. --- **3️⃣ Recursion + Memoization (Top-Down Approach)** **Plan**: 1. Pre-count the number of zeroes (`zeroCount`) and ones (`oneCount`) for each string. 2. Create a recursive function `dfs(index, mRemaining, nRemaining)` that returns the **maximum number of strings**you can pick starting from `index` if you still have `mRemaining` zeroes and `nRemaining` ones left to use. 3. At each call, you have two choices (if possible): * **Skip** the current string → `dfs(index + 1, mRemaining, nRemaining)` * **Pick** the current string (only if `zeroCount[index] <= mRemaining` and `oneCount[index] <= nRemaining`) → `1 + dfs(index + 1, mRemaining - zeroCount[index], nRemaining - oneCount[index])` 4. Use a memo (e.g., a dictionary or a 3D array) keyed by `(index, mRemaining, nRemaining)` to store results and avoid re-computation. **JavaScript Code**: ```js /** * Returns the maximum number of strings that can be formed from 'strs' * given at most m zeroes and n ones, using recursion + memoization. * * @param {string[]} strs - The array of binary strings. * @param {number} m - Maximum number of zeroes allowed. * @param {number} n - Maximum number of ones allowed. * @return {number} - The maximum number of strings you can form. */ function findMaxFormTopDown(strs, m, n) { const length = strs.length; // Precompute number of zeroes and ones for each string const counts = strs.map(str => { const zeroCount = [...str].filter(ch => ch === '0').length; const oneCount = str.length - zeroCount; // or filter '1' return { zeroCount, oneCount }; }); // Memo object: key -> (index, mRemaining, nRemaining), value -> max strings const memo = {}; /** * Recursive helper * @param {number} index - current string index * @param {number} mRemaining - remaining zero budget * @param {number} nRemaining - remaining one budget * @return {number} - maximum number of strings from this index onward */ function dfs(index, mRemaining, nRemaining) { // Base case if (index === length) { return 0; } const key = `${index}-${mRemaining}-${nRemaining}`; if (key in memo) { return memo[key]; } // Option 1: Skip current string let best = dfs(index + 1, mRemaining, nRemaining); // Option 2: Pick current string (if possible) const { zeroCount, oneCount } = counts[index]; if (zeroCount <= mRemaining && oneCount <= nRemaining) { best = Math.max( best, 1 + dfs(index + 1, mRemaining - zeroCount, nRemaining - oneCount) ); } memo[key] = best; return best; } return dfs(0, m, n); } // Example usage: console.log(findMaxFormTopDown(["10","0001","111001","1","0"], 5, 3)); // Example result console.log(findMaxFormTopDown(["10","0","1"], 1, 1)); // e.g., 2 ``` ### Explanation * We map each string to its count of zeroes and ones, stored in `counts[index]`. * `dfs(index, mRemaining, nRemaining)` tries skipping or picking the current string and returns the maximum possible count. * We memoize results to avoid exponential blow-up. **Time Complexity**: * Without memo, it’s `O(2^length)` in the worst case. * **With memo**: We have up to `length` (for index) \* `m` (for zeroes) \* `n` (for ones) states. Each state is computed once, and within each state, we do a constant amount of work. * Thus, the complexity is `O(length * m * n)`. **Space Complexity**: * The recursion depth is `O(length)` in the worst case. * The memo itself can hold up to `O(length * m * n)` entries. --- **4️⃣ Tabulation (Bottom-Up Approach)** We can solve this using a 2D DP array where: * `dp[i][j]` = the **maximum number of strings** we can form with `i` zeroes and `j` ones. * We iterate through each string (each has some `zeroCount`, `oneCount`), and update the `dp` table in *reverse* order (from `m -> zeroCount`, `n -> oneCount`) to avoid reusing the same string multiple times in the same iteration. **Idea**: 1. Initialize a 2D array `dp` of size `(m+1) x (n+1)` to all zeros. 2. For each string in `strs` (with some `(z, o)`): * Traverse `i` from `m` down to `z`, and `j` from `n` down to `o`. * Update `dp[i][j] = max(dp[i][j], 1 + dp[i - z][j - o])`. 3. `dp[m][n]` will be our result. **Why reverse order?** Because if we go in increasing order, we might reuse the same string more than once. Going backward ensures each string can only be counted once. **JavaScript Code**: ```js /** * Returns the maximum number of strings that can be formed from 'strs' * given at most m zeroes and n ones, using a bottom-up (tabulation) approach. * * @param {string[]} strs * @param {number} m * @param {number} n * @return {number} */ function findMaxFormBottomUp(strs, m, n) { // dp[i][j] = maximum subset size with i zeroes and j ones const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); // Precompute zeroCount and oneCount for each string const counts = strs.map(str => { const zeroCount = [...str].filter(ch => ch === '0').length; const oneCount = str.length - zeroCount; return { zeroCount, oneCount }; }); for (let { zeroCount, oneCount } of counts) { // Traverse backwards for (let i = m; i >= zeroCount; i--) { for (let j = n; j >= oneCount; j--) { dp[i][j] = Math.max( dp[i][j], 1 + dp[i - zeroCount][j - oneCount] ); } } } return dp[m][n]; } // Example usage: console.log(findMaxFormBottomUp(["10","0001","111001","1","0"], 5, 3)); console.log(findMaxFormBottomUp(["10","0","1"], 1, 1)); ``` ### Explanation * We have a 2D DP table. Each entry `dp[i][j]` tells us the best we can do with `i` zeroes and `j` ones. * For each string, we try to “take” it by updating the DP table from the top-right to bottom-left to avoid over-counting. **Time Complexity**: * We iterate over each of the `strs` (let’s say length = `k`), and for each, we potentially iterate over all `(m+1)*(n+1)`states. * So the complexity is `O(k * m * n)`. **Space Complexity**: * The 2D array `dp` has size `(m+1)*(n+1)`. * Thus `O(m*n)`. --- **5️⃣ Optimizing Space Complexity** In the bottom-up solution, we already use a **2D DP array** of size `(m+1) x (n+1)`. We do need both dimensions because we have two constraints (zeroes and ones). We don’t have a straightforward way to reduce this to a single dimension unless we only had one capacity constraint. In some problems, you might reduce a 2D knapsack to 1D if you only had one capacity dimension. But here we have two dimensions `(m,n)` – the budget of zeroes and ones. We *do* already do an “in-place update” in the 2D array in reverse order, which is typically the space-optimized approach for a knapsack with multiple constraints. Hence, **the 2D DP array is effectively the space-optimized approach** for two constraints. --- **6️⃣ Time Complexity Analysis** 1. **Naive Recursion** * Potentially tries all subsets. * Time Complexity: `O(2^k)` where `k` is the number of strings. 2. **Recursion + Memoization (Top-Down)** * We have `k` (index range), `m+1` possible zero budgets, and `n+1` possible one budgets. * Time Complexity: `O(k * m * n)`. * Space Complexity: up to `O(k * m * n)` for memo storage + recursion stack. 3. **Tabulation (Bottom-Up)** * We iterate through each string (k times) and update an `(m+1) x (n+1)` array. * Time Complexity: `O(k * m * n)`. * Space Complexity: `O(m * n)`. 4. **Space Optimization** * Because we have two resource constraints (`m` and `n`), our DP table remains 2D. We’re already modifying it in-place. * We can’t trivially reduce `(m+1)*(n+1)` to a single dimension without losing correctness. * Therefore, `O(m * n)` is typically the best we can do for the space complexity in this two-constraint knapsack problem. --- ## Conclusion * **Ones and Zeroes** is a classic 0/1 knapsack variant with two constraints: the number of 0’s and 1’s. * You can solve it via **Top-Down with Memo** or **Bottom-Up with a 2D DP array**. * Both approaches give `O(k * m * n)` time complexity, where `k` is the number of binary strings, `m` is the zero budget, and `n` is the one budget. * The **bottom-up approach** with a **2D DP** is often considered more straightforward to implement for production code, especially for knapsack-like problems with multiple constraints.