LeetCode 474: Ones and Zeroes

Problem Restatement

We are given an array of binary strings:

strs

We are also given two integers:

m
n

We can choose some strings from strs.

The chosen strings must use at most:

m zeros
n ones

Each string can be chosen at most once.

We need to return the largest possible number of strings we can choose. The official problem asks for the size of the largest subset of strs with at most m zeroes and n ones.

Input and Output

Function shape:

def findMaxForm(strs: list[str], m: int, n: int) -> int:
    ...

Examples

Example 1:

strs = ["10", "0001", "111001", "1", "0"]
m = 5
n = 3

One valid choice is:

"10", "0001", "1", "0"

Zero count:

"10"   -> 1 zero
"0001" -> 3 zeros
"1"    -> 0 zeros
"0"    -> 1 zero

total zeros = 5

One count:

"10"   -> 1 one
"0001" -> 1 one
"1"    -> 1 one
"0"    -> 0 ones

total ones = 3

We chose 4 strings.

Answer:

4

Example 2:

strs = ["10", "0", "1"]
m = 1
n = 1

We could choose "10" alone.

But a better choice is:

"0", "1"

This uses one zero and one one, and chooses two strings.

Answer:

2

First Thought: Try Every Subset

A direct idea is to generate every subset of strs.

For each subset:

1. Count all zeros.
2. Count all ones.
3. If both counts fit within m and n, update the best subset size.

This is correct, but it is too slow.

If there are k strings, then there are:

2^k

subsets.

Since the number of strings can be large, brute force is not practical. The older statement lists up to 600 strings and both m and n up to 100.

Key Insight

This is a 0/1 knapsack problem with two resource limits.

Each string is an item.

Its cost is:

number of zeros
number of ones

Its value is:

1

because choosing one string increases the subset size by one.

We need the maximum total value while staying within two budgets: zeros and ones.

So we use dynamic programming.

Let:

dp[i][j]

mean:

the maximum number of strings we can choose using at most i zeros and j ones

Algorithm

Create a 2D DP table:

dp = [[0] * (n + 1) for _ in range(m + 1)]

For each string s:

1. Count its zeros and ones.
2. Update the DP table in reverse order.
3. For each possible zero budget i and one budget j, decide whether taking this string improves the answer.

The transition is:

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

We iterate backward so each string is used at most once.

Why Reverse Order Matters

Suppose we update dp from small budgets to large budgets.

Then after using the current string once, the updated value could be used again in the same iteration.

That would allow one string to be chosen multiple times.

But this is a 0/1 problem: each string can be used at most once.

So we update backward:

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

This ensures that when we compute dp[i][j], the previous state:

dp[i - zeros][j - ones]

still comes from before considering the current string.

Walkthrough

Use:

strs = ["10", "0", "1"]
m = 1
n = 1

Start:

dp = [
    [0, 0],
    [0, 0],
]

Process "10".

It has:

zeros = 1
ones = 1

So:

dp[1][1] = 1

Process "0".

It has:

zeros = 1
ones = 0

Update:

dp[1][0] = 1
dp[1][1] = max(1, dp[0][1] + 1) = 1

Process "1".

It has:

zeros = 0
ones = 1

Update:

dp[0][1] = 1
dp[1][1] = max(1, dp[1][0] + 1) = 2

The final answer is:

dp[1][1] = 2

Correctness

The DP state dp[i][j] stores the maximum number of strings that can be selected using at most i zeros and j ones among the strings already processed.

For a new string with zeros zeros and ones ones, there are two choices.

We can skip it, leaving dp[i][j] unchanged.

Or, if i >= zeros and j >= ones, we can take it. Then the remaining budget before taking it is:

i - zeros
j - ones

The best subset for that remaining budget has size:

dp[i - zeros][j - ones]

Taking the current string adds one more selected string.

The transition takes the better of these two choices.

Because we process every string once and update budgets backward, no string can be used more than once.

Therefore, after all strings are processed, dp[m][n] is the maximum subset size that satisfies the zero and one limits.

Complexity

Let:

k = len(strs)
L = maximum length of a string

Implementation

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):
                    dp[i][j] = max(
                        dp[i][j],
                        dp[i - zeros][j - ones] + 1,
                    )

        return dp[m][n]

Code Explanation

We create the DP table:

dp = [[0] * (n + 1) for _ in range(m + 1)]

The row index is the zero budget.

The column index is the one budget.

For each string, we count zeros:

zeros = s.count("0")

Since the string is binary, the number of ones is:

ones = len(s) - zeros

Then we update budgets backward:

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

The update means:

take this string if it improves the best answer for this budget

Finally:

return dp[m][n]

returns the largest subset size under the full budget.

Testing

def run_tests():
    s = Solution()

    assert s.findMaxForm(
        ["10", "0001", "111001", "1", "0"],
        5,
        3,
    ) == 4

    assert s.findMaxForm(
        ["10", "0", "1"],
        1,
        1,
    ) == 2

    assert s.findMaxForm(
        ["0", "0", "1", "1"],
        2,
        2,
    ) == 4

    assert s.findMaxForm(
        ["00", "000"],
        1,
        10,
    ) == 0

    assert s.findMaxForm(
        ["1", "11", "111"],
        0,
        3,
    ) == 2

    assert s.findMaxForm(
        [],
        5,
        5,
    ) == 0

    print("all tests passed")

run_tests()

Test meaning: