LeetCode 474 - Ones and Zeroes

Difficulty: 🟡 Medium
Topics: Array, String, Dynamic Programming

Solution

Problem Understanding

This problem asks us to select the largest possible subset of binary strings while staying within two resource constraints.

Each string consumes a certain number of 0 characters and a certain number of 1 characters. We are given two limits:

m, the maximum number of zeros we can use
n, the maximum number of ones we can use

Our goal is to maximize how many strings we include in the subset without exceeding either limit.

For example, if a string contains two zeros and three ones, adding it to the subset increases our total zero usage by 2 and our total one usage by 3. We may only include the string if both totals remain within the allowed limits.

This is not asking for the longest concatenated string or the maximum total characters. The objective is specifically the number of strings selected.

The input consists of:

strs, an array of binary strings
m, the maximum allowed zeros
n, the maximum allowed ones

The output is a single integer representing the size of the largest valid subset.

The constraints are important:

Up to 600 strings
Each string length up to 100
m and n up to 100

These limits strongly suggest that exponential subset enumeration will not work. A brute-force search over all subsets would require checking up to 2^600 combinations, which is impossible.

The relatively small values of m and n are the key observation. Since both are at most 100, we can build a dynamic programming solution whose state depends on the available zeros and ones.

Several edge cases are important:

A string may contain more zeros or ones than allowed, meaning it can never be chosen.
Multiple identical strings may appear, and each occurrence must be treated independently.
The optimal solution may skip long strings in favor of many short strings.
Some strings may contain only zeros or only ones.
The subset can contain at most all strings, but resource limits often prevent that.

Approaches

Brute Force

The most direct approach is to try every possible subset of strings.

For each subset, we count the total number of zeros and ones used. If both totals stay within the limits, we compare the subset size against the current best answer.

This works because every possible subset is examined, so the optimal subset must eventually be found.

However, the number of subsets grows exponentially. With k strings, there are 2^k possible subsets. Since k can be as large as 600, this approach is computationally infeasible.

Even with pruning or memoization, a naive recursive search would still struggle due to the enormous state space.

Optimal Dynamic Programming Approach

The key insight is that this problem is structurally identical to a 0/1 knapsack problem with two constraints instead of one.

In a traditional knapsack problem:

Each item has a weight
Each item has a value
We maximize value without exceeding capacity

Here:

Each string consumes zeros and ones
Each string contributes value 1 because selecting any string increases subset size by one
We maximize the number of selected strings

This becomes a two-dimensional knapsack problem.

We define:

dp[i][j] as the maximum number of strings we can select using at most i zeros and j ones

For each string:

Count how many zeros and ones it contains
Update the DP table in reverse order
Decide whether including the current string improves the answer

The reverse iteration is essential because each string may only be used once.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^k * k)	O(k)	Tries every subset of strings
Optimal	O(k * m * n)	O(m * n)	Two-dimensional 0/1 knapsack DP

Here, k represents the number of strings.

Algorithm Walkthrough

Create a two-dimensional DP table.

We create dp[m + 1][n + 1], where each entry stores the maximum number of strings achievable with a given zero and one budget.

Initially, all values are 0 because selecting no strings is always valid. 2. Process each string one at a time.

For every string in strs, count:

how many zeros it contains
how many ones it contains

These counts represent the "cost" of selecting the string. 3. Traverse the DP table in reverse order.

For every possible zero capacity from m down to zero_count, and every one capacity from n down to one_count, we evaluate whether taking the current string improves the solution.

Reverse traversal is critical because it prevents using the same string multiple times during a single iteration. 4. Update the DP state.

The transition is:

$dp[i][j] = \max(dp[i][j],\ dp[i-zeroCount][j-oneCount] + 1)$

This means:

either do not take the current string
or take it and add one to the best previous solution

Continue until all strings are processed.

After processing every string, dp[m][n] contains the maximum subset size achievable within the limits.

Why it works

The DP table maintains the invariant that dp[i][j] always represents the best achievable subset size using at most i zeros and j ones from the strings processed so far.

Because every string is considered exactly once, and every valid capacity combination is updated correctly, the algorithm explores all feasible combinations without duplication. Reverse iteration guarantees 0/1 behavior, meaning each string can either be selected once or skipped.

Python Solution

from typing import List

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # dp[i][j] = maximum number of strings
        # using at most i zeros and j ones
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for binary_string in strs:
            zero_count = binary_string.count('0')
            one_count = binary_string.count('1')

            # Reverse iteration ensures each string
            # is used at most once
            for zeros in range(m, zero_count - 1, -1):
                for ones in range(n, one_count - 1, -1):
                    dp[zeros][ones] = max(
                        dp[zeros][ones],
                        dp[zeros - zero_count][ones - one_count] + 1
                    )

        return dp[m][n]

The implementation begins by creating a two-dimensional DP table. Each cell represents the best subset size achievable under a particular zero and one budget.

For every string, we count its zeros and ones. These counts determine whether the string can fit into a given capacity state.

The nested reverse loops are the most important part of the implementation. By iterating backward, we ensure that updates for the current string do not affect future computations within the same iteration. This preserves the 0/1 knapsack property.

At each state, we compare:

the current best value without taking the string
the value obtained by taking the string

The maximum of these two becomes the new DP value.

Finally, the answer is stored in dp[m][n], which represents the best achievable subset under the full resource limits.

Go Solution

func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)

	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	for _, s := range strs {
		zeroCount := 0
		oneCount := 0

		for _, ch := range s {
			if ch == '0' {
				zeroCount++
			} else {
				oneCount++
			}
		}

		for zeros := m; zeros >= zeroCount; zeros-- {
			for ones := n; ones >= oneCount; ones-- {
				candidate := dp[zeros-zeroCount][ones-oneCount] + 1

				if candidate > dp[zeros][ones] {
					dp[zeros][ones] = candidate
				}
			}
		}
	}

	return dp[m][n]
}

The Go implementation follows the same algorithmic structure as the Python solution.

Instead of Python lists, Go uses slices to build the two-dimensional DP table. String traversal is done using a range loop over characters.

Go does not provide a built-in max function for integers, so the comparison is written explicitly with an if statement.

There are no integer overflow concerns because the maximum possible answer is at most 600, which easily fits within Go's int type.

Worked Examples

Example 1

Input:

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

We process each string one at a time.

Step 1: Process `"10"`

zeros = 1
ones = 1

Relevant DP updates:

zeros	ones	New Value
1	1	1
2	2	1
5	3	1

This means any capacity that can afford one zero and one one can now achieve subset size 1.

Step 2: Process `"0001"`

zeros = 3
ones = 1

Important updates:

zeros	ones	Previous	Candidate	Result
4	2	1	2	2
5	3	1	2	2

Now we can combine "10" and "0001".

Step 3: Process `"111001"`

zeros = 2
ones = 4

This string requires four ones, but n = 3.

Therefore, it cannot fit into any valid state and contributes nothing.

Step 4: Process `"1"`

zeros = 0
ones = 1

Important updates:

zeros	ones	Previous	Candidate	Result
4	3	2	3	3
5	3	2	3	3

Step 5: Process `"0"`

zeros = 1
ones = 0

Important updates:

zeros	ones	Previous	Candidate	Result
5	3	3	4	4

Final answer:

The optimal subset is:

{"10", "0001", "1", "0"}

Example 2

Input:

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

Initial DP table:

zeros\ones	0	1
0	0	0
1	0	0

Process `"10"`

zeros = 1
ones = 1

Update:

zeros	ones	Result
1	1	1

Process `"0"`

zeros = 1
ones = 0

Update:

zeros	ones	Result
1	0	1

Process `"1"`

zeros = 0
ones = 1

Update:

zeros	ones	Previous	Candidate	Result
1	1	1	2	2

Final answer:

The optimal subset is:

{"0", "1"}

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k * m * n)	For each string, we iterate through the DP table
Space	O(m * n)	The DP table stores one state per zero/one capacity pair

Here, k is the number of strings.

The preprocessing step of counting zeros and ones contributes additional work proportional to total string length, but this is dominated by the DP transitions.

Since m and n are at most 100, the DP table contains at most 10,201 states, making this approach highly efficient for the given constraints.

Test Cases

from typing import List

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 = s.count('1')

            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]

solution = Solution()

assert solution.findMaxForm(
    ["10", "0001", "111001", "1", "0"], 5, 3
) == 4  # Provided example 1

assert solution.findMaxForm(
    ["10", "0", "1"], 1, 1
) == 2  # Provided example 2

assert solution.findMaxForm(
    ["10"], 1, 1
) == 1  # Single string fits exactly

assert solution.findMaxForm(
    ["10"], 0, 0
) == 0  # No capacity available

assert solution.findMaxForm(
    ["111"], 3, 2
) == 0  # String exceeds one limit

assert solution.findMaxForm(
    ["000"], 2, 5
) == 0  # String exceeds zero limit

assert solution.findMaxForm(
    ["0", "0", "1", "1"], 2, 2
) == 4  # Can take all strings

assert solution.findMaxForm(
    ["10", "10", "10"], 2, 2
) == 2  # Duplicate strings handled independently

assert solution.findMaxForm(
    ["0", "1", "01", "10"], 2, 2
) == 3  # Must choose optimal combination

assert solution.findMaxForm(
    ["00", "11", "01", "10"], 2, 2
) == 2  # Multiple valid optimal subsets

assert solution.findMaxForm(
    ["0"] * 100, 50, 0
) == 50  # Large number of simple strings

assert solution.findMaxForm(
    ["1"] * 100, 0, 75
) == 75  # Ones-only capacity constraint

assert solution.findMaxForm(
    ["10"] * 600, 100, 100
) == 100  # Stress test near constraints

Test Summary

Test	Why
`["10","0001","111001","1","0"]`	Validates provided example
`["10","0","1"]`	Validates second provided example
Single exact-fit string	Tests minimal valid inclusion
Zero capacities	Ensures empty subset handling
String exceeding ones limit	Verifies invalid strings are skipped
String exceeding zeros limit	Verifies zero constraint handling
All strings fit	Confirms full selection possible
Duplicate strings	Ensures each occurrence treated separately
Mixed combinations	Tests optimal decision making
Multiple optimal answers	Confirms correctness regardless of subset identity
Large zeros-only input	Stress tests repeated updates
Large ones-only input	Tests one-dimensional behavior
Near-constraint stress test	Validates performance scalability

Edge Cases

One important edge case occurs when a string individually exceeds the resource limits. For example, if m = 2 and a string contains three zeros, that string can never be selected. A naive implementation might still attempt invalid transitions or index negative positions in the DP table. This implementation avoids the issue because the reverse loops only execute when the capacity is large enough to fit the string.

Another important case is duplicate strings. Multiple identical strings may appear in the input, but each occurrence represents a separate selectable item. A buggy solution might incorrectly deduplicate them using a set. The dynamic programming approach processes every string independently, so duplicates are handled correctly.

A third subtle edge case involves reverse iteration. If the DP table were updated in forward order, a string could effectively be reused multiple times within the same iteration, turning the problem into an unbounded knapsack. Reverse traversal guarantees that each string contributes at most once to any state update.

A final edge case occurs when capacities are very small, such as m = 0 or n = 0. In those situations, only strings containing the allowed character type may be selected. The DP formulation naturally handles this because transitions only occur when sufficient capacity exists.

LeetCode 474 - Ones and Zeroes

Solution

Problem Understanding

Approaches

Brute Force

Optimal Dynamic Programming Approach

Approach Comparison

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Process "10"

Step 2: Process "0001"

Step 3: Process "111001"

Step 4: Process "1"

Step 5: Process "0"

Example 2

Process "10"

Process "0"

Process "1"

Complexity Analysis

Test Cases

Test Summary

Edge Cases

Step 1: Process `"10"`

Step 2: Process `"0001"`

Step 3: Process `"111001"`

Step 4: Process `"1"`

Step 5: Process `"0"`

Process `"10"`

Process `"0"`

Process `"1"`