474. Ones and Zeroes

Problem¶

Choose the maximum number of strings from strs whose combined counts use at most m zeroes and n ones.

strs = ["10", "0", "1"], m = 1, n = 1
choose ["0", "1"] -> 2

Key trick¶

Use two-dimensional 0/1 knapsack: process each string once, updating both budget dimensions backward so the string cannot be chosen again during the same iteration.

Trap¶

Updating budgets forward lets one string be reused. The empty subset also has size 0, not 1.

Why is it interesting?¶

It combines two resource limits with the iteration-order detail that makes space-efficient 0/1 knapsack work.

Python solution¶

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

            # Descend so each string contributes at most once.
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(
                        dp[i][j],
                        dp[i - zeros][j - ones] + 1,
                    )

        return dp[m][n]

Time: \(O(\sum |s| + |\text{strs}|mn)\). Space: \(O(mn)\).

Comment on my solution¶

Your DP state is right, but the transition considers every string at every budget without tracking whether it was already chosen. That turns the problem into unbounded knapsack and produces answers larger than the input. Start every state at 0, then process strings one at a time with descending budget loops.

# Ideas:
# - it seems to be 2D knapsack DP
#   - dp[i][j] = max number of strings such that num of 0's <= i and num of 1s <= j
#   - answer would be dp[m][n]
#   - but what is the transition
#   - dp[i][j] = max(dp[i - num_0_s][j - num_1_s] for valid s in strs + 1)


# Wrong Answer: 7/77 testcases passed
# ["10","0001","111001","1","0"], 5, 3
# Output: 9
# Expected: 4
class Solution:
    def findMaxForm(self, strs: list[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = 1 # empty set

        for i in range(m + 1):
            for j in range(n + 1):
                for s in strs:
                    num_0_s = sum(1 for b in s if b == "0")
                    num_1_s = sum(1 for b in s if b == "1")
                    if num_0_s <= i and num_1_s <= j:
                        dp[i][j] = max(dp[i][j], dp[i - num_0_s][j - num_1_s] + 1)
        return dp[m][n]

Extra¶

Complement on knapsack problems¶

• Why doing the loop backward ensure we don't string twice? It's not clear to me. What am I missing?
• What about strs containing "01" and "10" for instance which gives the same zeroes and ones? Are they counted twice? What am I missing?
• This is the 4^th knapsack problem I do (Coin change, Coin Change II, Combination Sum IV) and it's still not clear how should I think, approach and solve this kind of problem. When to pick the right iteration order? When are we counting unorderer sequences? What am I missing? It's seems that I'm missing some basic understanding of combinatorics.

You are not missing a combinatorics prerequisite. The key distinction is what one DP update is allowed to read. Loop order controls that.

Why does going backward prevent reuse?¶

Suppose the only string is "01", and both budgets are 2. Its cost is (1 zero, 1 one).

If budgets go forward, updating dp[1][1] to 1 happens before updating dp[2][2]. The latter can read the newly updated dp[1][1] and add the same string again:

dp[1][1] = dp[0][0] + 1 = 1
dp[2][2] = dp[1][1] + 1 = 2  # Reused "01"

If both budgets go backward, dp[2][2] is updated first. At that point, dp[1][1] still describes the result before processing "01":

dp[2][2] = old dp[1][1] + 1 = 1
dp[1][1] = old dp[0][0] + 1 = 1

That is the invariant: while processing one string, every source state must still be from before that string.

What about "01" and "10"?¶

They are two distinct input strings with the same cost. Processing "01" can produce a result of 1; processing "10" afterward can extend it to 2.

strs = ["01", "10"], m = 2, n = 2 -> 2
strs = ["01"],       m = 2, n = 2 -> 1

Backward iteration prevents reusing the current input item. It does not prevent using a different item that happens to have the same cost. Even two occurrences of "01" in strs are two available items.

How to choose the knapsack loop order¶

Ask two separate questions:

• Can I use a choice once or repeatedly?
  • Once: process choices outside, budgets backward.
  • Repeatedly: budgets may go forward, allowing the current choice to extend a state it just created.
• If counting, does order distinguish answers?
  • No: process choices outside. Each combination is built in one fixed choice order.
  • Yes: process the total outside, then try each possible last choice. Different orders become different paths.

Your four problems fit this map:

For the counting distinction, consider coins 1, 2 and target 3:

Combinations:      [1, 1, 1], [1, 2]         -> 2
Ordered sequences: [1, 1, 1], [1, 2], [2, 1] -> 3

The mental model: write down what a DP state represents, then ask whether an update should be allowed to use a state created earlier in the same choice's iteration. That decides backward versus forward. Separately, decide whether choices have a fixed processing order or every choice can be the last step. That decides combinations versus ordered sequences.