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) andn(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 solution is acceptable rather than exponential brute force (where is the number of strings).
mandnare 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 possible subsets and check validity for each. With strs.length up to 600, this is computationally impossible ().
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
- State Definition: Let
dp[i][j]be the maximum number of strings we can include using at mostizeros andjones. The dimensions will range from tomand ton. Initialize this table with all zeros (representing a subset size of 0). - Item Processing: Iterate through each string in the input list. For every string, count its number of ‘0’s (
z) and ‘1’s (o). - 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
ifrommdown toz, andjfromndown too. - Transition: For each valid cell
(i, j): If including this string fits (i >= zandj >= o), we check if picking it yields a better result:
dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1) - 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: , where is the number of strings in
strs. We iterate through each string once (), and for each, we potentially update a grid of size . Given constraints ( operations), this fits comfortably within time limits. - Space Complexity: for the DP table storing counts of zeros and ones up to
mandn.
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
mdown toz_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
dptable 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).