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.
Intuition
This is a 0/1 knapsack with two weight dimensions — zeros and ones — instead of one. Each string has a 'cost' in zeros and a 'cost' in ones, and a 'value' of 1 (you want to maximise the count of strings selected). The DP table dp[z][o] represents the maximum number of strings you can select using at most z zeros and o ones. For each string, you decide whether to include it (paying its zero and one cost) or skip it — exactly the knapsack choice.
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
Count the zeros and ones in each string upfront
For each string in strs, count how many 0s and 1s it contains. Store these counts — they are the two 'weights' for the knapsack. This avoids recounting during the DP transitions.
Fill a 2D DP table with reverse iteration
Initialize dp[z][o] = 0 for all 0 <= z <= m and 0 <= o <= n. For each string with z0 zeros and o1 ones, iterate z from m down to z0 and o from n down to o1. Update dp[z][o] = max(dp[z][o], dp[z - z0][o - o1] + 1). The reverse iteration ensures each string is used at most once (0/1 knapsack, not unbounded).
Read the answer from `dp[m][n]`
After processing all strings, dp[m][n] holds the maximum subset size. Time is O(len(strs) m n). Space is O(m * n) for the DP table.
Solution
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.