Ones and Zeroes — 2D 0/1 Knapsack with Two Capacities

Problem Statement#

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 the chosen strings together contain at most m zeros and n ones.

A string x is a subset of y if all elements of x are also elements of y.

Example: strs = ["10","0001","111001","1","0"], m = 5, n = 3 returns 4. The largest subset is {"10", "0001", "1", "0"} with 4 zeros and 3 ones, satisfying the constraint.

Example: strs = ["10","0","1"], m = 1, n = 1 returns 2. The subset {"0", "1"} uses 1 zero and 1 one.

Constraints: 1 is less than or equal to strs.length is less than or equal to 600, each string up to length 100, 1 is less than or equal to m, n is less than or equal to 100. The bound is tuned for an O(strs.length * m * n) DP.

Why This Problem Matters#

Ones and Zeroes is the cleanest demonstration of multi-capacity 0/1 knapsack. Google, Amazon, and Meta ask it because it tests whether a candidate can extend the standard one-resource knapsack template to two resources without reaching for a fundamentally new algorithm.

The pattern generalizes: any problem where each item costs multiple kinds of resources (CPU and memory, weight and volume, zeros and ones) can be solved with a multi-dimensional knapsack DP. After mastering this one, you can attack budget-allocation, packing, and scheduling problems with the same template.

The Core Insight (Recurrence)#

Each binary string is an "item" with two costs: number of zeros and number of ones. The capacities are m zeros and n ones. We want to maximize the count of items chosen.

Define dp[i][j] as the maximum number of strings we can select using at most i zeros and j ones from the strings processed so far. For each new string with z zeros and o ones, the transition is:

dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1) for all i, j with i >= z and j >= o.

Either we skip the string (left side keeps its value) or we take it (gaining 1 toward the count, paying z zeros and o ones).

The 1D-collapsed table requires reverse iteration on both dimensions to preserve the 0/1 property — same logic as Partition Equal Subset Sum extended to two axes.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down: solve(i, zeros_left, ones_left) returns the max strings selectable from strs[i..] under the two budgets. Recurse into skip and take branches. Memoize on (i, zeros_left, ones_left) for O(L * m * n) time and O(L * m * n) memory plus stack, where L is len(strs).

Tabulation 3D: dp[L+1][m+1][n+1]. Cleanest mental model but uses lots of memory.

Tabulation 2D (collapsed): single dp[m+1][n+1] array. For each string compute (z, o), then loop i from m down to z and j from n down to o and update dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1). The double-reverse iteration is the load-bearing trick.

Why iterate descending on both axes? If you iterate ascending on either, the same string can be picked twice in a single update — that violates 0/1 and turns the answer into unbounded knapsack.

Visual Dry Run (DP Table Trace)#

Trace strs = ["10", "0", "1"], m = 1, n = 1. The DP table is 2x2 (indices 0..1 on both axes).

Initial: dp = [[0,0],[0,0]].

Process "10" with (z=1, o=1):

• i = 1, j = 1: dp[1][1] = max(0, dp[0][0] + 1) = 1.
• After: dp = [[0,0],[0,1]].

Process "0" with (z=1, o=0):

• i = 1, j = 1: dp[1][1] = max(1, dp[0][1] + 1) = max(1, 0 + 1) = 1.
• i = 1, j = 0: dp[1][0] = max(0, dp[0][0] + 1) = 1.
• After: dp = [[0,0],[1,1]].

Process "1" with (z=0, o=1):

• i = 1, j = 1: dp[1][1] = max(1, dp[1][0] + 1) = 2.
• i = 0, j = 1: dp[0][1] = max(0, dp[0][0] + 1) = 1.
• After: dp = [[0,1],[1,2]].

Answer: dp[1][1] = 2, matching expected output.

Notice how processing "1" last let it combine with the existing "0" selection because we iterated i and j descending, ensuring each string is counted once.

Optimized Solution — Space-Optimized Python and JavaScript#

Python#

from typing import List
 
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):
                    take = dp[i - zeros][j - ones] + 1
                    if take > dp[i][j]:
                        dp[i][j] = take
        return dp[m][n]

JavaScript#

var findMaxForm = function (strs, m, n) {
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (const s of strs) {
    let zeros = 0;
    for (const ch of s) if (ch === '0') zeros += 1;
    const ones = s.length - zeros;
    for (let i = m; i >= zeros; i -= 1) {
      for (let j = n; j >= ones; j -= 1) {
        const take = dp[i - zeros][j - ones] + 1;
        if (take > dp[i][j]) dp[i][j] = take;
      }
    }
  }
  return dp[m][n];
};

Complexity Analysis#

• Time: O(L * m * n) where L is the number of input strings. Each string contributes an O(m * n) sweep. Counting zeros within each string adds O(total characters) one-time.
• Space: O(m * n) for the collapsed 2D table.
• Memoized recursion: same time but O(L * m * n) memory plus stack.
• For LeetCode constraints (L at most 600, m, n at most 100) we are bounded by 600 * 100 * 100 = 6 * 10^6 operations — comfortable.

Common Mistakes#

• Iterating ascending on either axis. That allows reusing the same string and turns the answer into unbounded knapsack.
• Counting ones with the wrong character. Use s.count('0') or count zeros explicitly; mixing zeros and ones inverts the constraint.
• Allocating dp[m][n] instead of dp[m+1][n+1]. Off-by-one is common; remember capacity 0 is a valid state.
• Forgetting that strings can be empty. An empty string costs 0 zeros and 0 ones and counts as 1 toward the answer for free — the DP handles it but watch for input variations.
• Sorting strs "to fit smaller items first." That has no effect on the answer for 0/1 knapsack; do not waste time on it.

Interview Tips#

• Open by labeling this as 0/1 knapsack with two capacities. That single sentence proves pattern recognition.
• Walk through why we iterate both axes descending. Many candidates code this on autopilot and miss the question; explaining it earns easy credit.
• Mention the 3D version (dp[i][zeros][ones]) as the "natural" formulation, then justify the collapse to 2D.
• Discuss the constant-factor tradeoff: counting zeros once per string vs. recomputing inside the loop.

Follow-up Questions#

• Generalize to k binary alphabets (zeros, ones, twos, ...). The DP becomes k-dimensional.
• Each string has a non-negative weight; maximize total weight rather than count. Replace + 1 with + weight[s].
• Allow each string to be picked multiple times (unbounded knapsack). Iterate both axes ascending.
• Reconstruct which strings were chosen. Store predecessor info or run a second pass walking the table.

Key Takeaways#

• Ones and Zeroes is a textbook two-capacity 0/1 knapsack with a clean two-axis recurrence and reverse iteration on both axes.
• The state dp[i][j] represents the max strings selectable using at most i zeros and j ones — generalizes the single-capacity knapsack.
• Time is O(L * m * n); space collapses to O(m * n) with the rolling-table trick — the senior-level optimization.
• Reverse iteration on both axes is non-negotiable for the 0/1 property; reversing only one axis silently breaks correctness.
• The pattern extends to any multi-resource selection problem and is a strong signal of DP fluency in interviews.
• Prefer the 2D-collapsed table over the 3D variant under interview pressure — it is shorter and faster.