Ones and Zeroes
Ones and Zeroes: 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 subset contains at most m zeros and n ones in total.
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] consists only of digits '0' and '1'.
- 1 <= m, n <= 100
Intuition
Ones and zeroes selects the largest subset of binary strings whose total zeros stay within m and total ones within n. Each string is used at most once.
That framing is knapsack — but with two independent capacity limits instead of one. A string's cost is a pair: how many zeros it consumes and how many ones. Its value is always 1, since the objective is to maximise the count of strings selected rather than any per-string worth.
So the DP table gains a dimension:
- dp[z][o] is the largest subset achievable using at most z zeros and o ones.
One string is either taken or skipped, exactly as in 0/1 knapsack. Taking it consumes both budgets and adds 1 to the count.
The detail that enforces at-most-once is the iteration direction. With the table collapsed to two dimensions, both loops must run downward — from m to the string's zero count, and from n to its one count. Iterating upward would let a cell already updated by this string be read again, letting one string be selected twice and silently converting the problem to unbounded knapsack.
That is the same rule as the one-dimensional 0/1 knapsack, applied on both axes rather than one.
Count each string's zeros and ones once up front, rather than recounting inside the loops.
The tell is: you are selecting items from a list, each with a cost in two dimensions, and you want to maximise the count (or total value) under two budget constraints. This is the 2D knapsack. The single-dimension version is the classic 0/1 knapsack; adding a second dimension just adds another loop. The reverse-iteration trick for 0/1 (not unbounded) knapsack applies to each dimension.
Approach
Before reading on: price up what counting everything costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(L * m * n) time and O(m * n) space.
See it as two-dimensional knapsack
Each string costs zeros and ones, and is worth 1. The only difference from ordinary 0/1 knapsack is a second capacity axis — the take-or-skip structure is unchanged.
Count each string once up front
Compute the zero and one counts for every string before the DP begins. Recounting inside the nested loops would multiply the work by the string length for no benefit.
Define the two-dimensional state
dp[z][o] is the largest subset using at most z zeros and o ones, initialised to 0 everywhere. The value is a count of strings, not a sum of weights.
Take or skip each string
For a string costing z0 zeros and o1 ones, dp[z][o] = max(dp[z][o], dp[z - z0][o - o1] + 1) where the budgets allow. Skipping is the existing value; taking adds one to a smaller state.
Iterate both loops downward
Sweep z from m down to z0 and o from n down to o1. Iterating upward lets a cell already updated by this string be read again, allowing the same string twice — the classic 0/1 knapsack error, on two axes.
Read the answer from dp[m][n]
The full-budget cell holds the maximum subset size. Because every entry already carries the best value for its budget, no final scan of the table is needed.
Cost of the tabulation
Each string sweeps the whole m × n table, giving O(len(strs) · m · n) time and O(m · n) space after the rolling-table optimisation.
Solution & live demo
Common pitfalls
Iterating forward instead of backward in the DP loops
for z in range(z0, m + 1):
for o in range(o1, n + 1):for z in range(m, z0 - 1, -1):
for o in range(n, o1 - 1, -1):Forward iteration lets the same string be counted multiple times in a single pass, turning this into an unbounded knapsack. Reverse iteration ensures each string's contribution propagates only once.
Confusing zeros and ones counts in the string
z0 = s.count('1')
o1 = s.count('0')z0 = s.count('0')
o1 = s.count('1')Swapping the counts assigns the zero budget to ones and vice versa. The DP table misallocates capacity, giving a wrong answer whenever m != n.
Initialising dp to -infinity instead of 0
dp = [[-float('inf')] * (n + 1) for _ in range(m + 1)]dp = [[0] * (n + 1) for _ in range(m + 1)]
The base state is 'zero strings selected using zero capacity', which has value 0, not -infinity. Negative infinity propagates through max operations and corrupts the table.
Edge cases
Its o1 = 0, so the inner loop over o runs for all values from n down to 0. The string only consumes zero-capacity.
m and nThe reverse loops start at m and n. If z0 > m or o1 > n, the loop condition z >= z0 or o >= o1 fails immediately, and the string is effectively skipped.
m = 0 and n = 0dp[0][0] = 0. No string can be selected because every non-empty string has at least one zero or one one.