Ones and Zeros

01-22-2026

Problem Statement

Given an array of binary stringsI.e. "1010", "001", "1", etc strs and two constraints m and n designating the max amount of 0s and 1s you can have, return the max number of strings you can include with respect to the constaints.

Solution

The correct path to solving this problem is given in the description. We want to maximize the number of strings we can take given the constraints. When you see a maximize or minimize in the problem, your brain should automatically be working towards a DP approach. Once you establish that DP is the way forward, the next step/framework is obvious. Before I say it, lets analyze some key characteristics of the problem:

  1. This is dynamic programming
  2. We have two constraints
  3. We want to include multiple strings
  4. Each string can either be totally included or totally excluded.

Remind you of anything? If you thought 0/1 Knapsack, then you are correct! A classic DP approach is exactly what we want here. Of course, there is some nuance here as we have two constraints now: the number of 0s and 1s. Luckily, if you were to read the note above on this type of knapsack, then it is only a slight modification.

Let dp[i][j] be the number of strings we can include with i 0s and j 1s, we need to find the key to building from the ground up. Well, it should make sense that if we have an item "1010", then we can include one more item than dp[curZeros - 2][curOnes - 2]. This makes sense, but there are still two glaring holes in this idea

  1. What are curZeros and curOnes?
  2. What about the constraint?

Of course, this is where the classic knapsack for loop comes in:

python
for curZeros in range(m, numZeros - 1, -1):
	for curOnes in range(n, numOnes - 1, -1):
		dp[i][j] = max(dp[i][j], 
						dp[curZeros - numZeros][curOnes - numOnes]
					)

This cleverly solves both problems, filling in all valid configs with the new possibility of adding this string in while respecting the constraints and not double counting itself with the reversed-iteration. Here is the full implementation:

python
dp = [[0] * (n+1) for _ in range(m+1)]
 
for s in strs:
	ones = s.count("1")
	zeros = len(s) - ones

	for i in range(m, zeros-1 , -1):
		for j in range(n, ones-1, -1):

			dp[i][j] = max(1+dp[i-zeros][j-ones], dp[i][j])

return dp[-1][-1]