Domain 2MediumCORE

Ones and Zeroes

We need to select the maximum number of strings from an input list such that their combined count of '0' characters does not exceed m and their combined count of '1' characters does not exceed n.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

474. Ones and Zeroes

Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 44.1%


Problem Breakdown

We need to select the maximum number of strings from an input list such that their combined count of ‘0’ characters does not exceed m and their combined count of ‘1’ characters does not exceed n.

Inputs:

  • A list of binary strings (strs).
  • Two integers representing capacity limits: m (zeros) and n (ones).

Output:

  • An integer representing the size of this maximum subset.

Constraints & Edge Cases:

  • The input array length is up to 600, string lengths up to 100. This suggests an O(K⋅m⋅n)O(K \cdot m \cdot n) solution is acceptable rather than exponential brute force (where KK is the number of strings).
  • m and n are small (up to 100).
  • Strings consist only of ‘0’ or ‘1’. No negative numbers, no empty strings per constraints.
  • We treat each string as a distinct item that can be picked at most once (even if duplicate values exist in the list), which is characteristic of the 0/1 Knapsack Problem.

Intuition

A brute-force approach would generate all 2K2^K possible subsets and check validity for each. With strs.length up to 600, this is computationally impossible (O(2K)O(2^{K})).

We need a way to build the solution incrementally without re-evaluating every combination from scratch. This structure—items with specific resource costs (zeros and ones) contributing value (count of items)—is identical to the Knapsack Problem. Specifically, it is a 2-dimensional Knapsack problem because we have two constraints (m zeros and n ones).

The key insight is that for each string, we decide whether including it improves our current best subset size given remaining capacity. We can use Dynamic Programming where the state represents how many items we can fit within specific resource limits. By iterating through strings one by one and updating a DP table based on their costs, we avoid recomputing subsets from scratch.

Approach

  1. State Definition: Let dp[i][j] be the maximum number of strings we can include using at most i zeros and j ones. The dimensions will range from 00 to m and 00 to n. Initialize this table with all zeros (representing a subset size of 0).
  2. Item Processing: Iterate through each string in the input list. For every string, count its number of ‘0’s (z) and ‘1’s (o).
  3. DP Update: We want to update our DP table considering this new item. To ensure we don’t use the same item multiple times for a single capacity state (which would violate the subset constraint), we iterate backwards through i from m down to z, and j from n down to o.
  4. Transition: For each valid cell (i, j): If including this string fits (i >= z and j >= o), we check if picking it yields a better result:
    dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1)
  5. Result: After processing all strings, the value at dp[m][n] will hold the maximum subset size possible within the given limits.

Complexity Analysis

  • Time Complexity: O(K⋅m⋅n)O(K \cdot m \cdot n), where KK is the number of strings in strs. We iterate through each string once (KK), and for each, we potentially update a grid of size (m+1)×(n+1)(m+1) \times (n+1). Given constraints (600×100×100=6⋅106600 \times 100 \times 100 = 6 \cdot 10^6 operations), this fits comfortably within time limits.
  • Space Complexity: O(m⋅n)O(m \cdot n) for the DP table storing counts of zeros and ones up to m and n.

Solution

from typing import List

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # Initialize DP table with 0s. 
        # dp[i][j] stores max subset size using at most i zeros and j ones.
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

        for s in strs:
            z_count = s.count('0')
            o_count = len(s) - z_count
            
            # Iterate backwards to ensure each string is used at most once per state.
            # Similar to the space-optimized 1D knapsack approach extended to 2 dimensions.
            for i in range(m, z_count - 1, -1):
                for j in range(n, o_count - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - z_count][j - o_count] + 1)

        return dp[m][n]

Edge Cases Handled

  • String costs exceed capacity: The inner loops range from m down to z_count. If a string requires more zeros than available (i < z_count), the loop condition prevents access, effectively skipping that item for those states. This is handled naturally by Python’s iteration bounds and index checks implicitly via logic flow (though strictly speaking we check indices before accessing).
  • Empty subset: Initialized dp table with 0s correctly represents a valid empty subset size of 0 if no strings fit the criteria.
  • Duplicate strings in input: The algorithm treats each string entry as an independent item to be picked or not, consistent with LeetCode’s definition of “subset” (indices matter).