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:

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.

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:

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):

                       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:

Pre-count the number of zeroes (zeroCount) and ones (oneCount) for each string.
Create a recursive function dfs(index, mRemaining, nRemaining) that returns the maximum number of stringsyou can pick starting from index if you still have mRemaining zeroes and nRemaining ones left to use.
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])
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:

/**
 * 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:

Initialize a 2D array dp of size (m+1) x (n+1) to all zeros.
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]).
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:

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

Naive Recursion
- Potentially tries all subsets.
- Time Complexity: O(2^k) where k is the number of strings.
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.
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).
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.