Problem Description

You have an array of binary strings (strings containing only '0's and '1's) and two integer limits: m for zeros and n for ones.

Your task is to find the maximum number of strings you can select from the array such that the total count of '0's across all selected strings doesn't exceed m, and the total count of '1's doesn't exceed n.

For example, if you have strings ["10", "0001", "111001", "1", "0"] with m = 5 and n = 3:

• String "10" has 1 zero and 1 one
• String "0001" has 3 zeros and 1 one
• String "111001" has 2 zeros and 4 ones
• String "1" has 0 zeros and 1 one
• String "0" has 1 zero and 0 ones

You need to select a subset of these strings where the total zeros ≤ 5 and total ones ≤ 3. The goal is to maximize the number of strings in your selection.

The solution uses dynamic programming with a 3D table f[i][j][k] where:

• i represents considering the first i strings
• j represents using at most j zeros
• k represents using at most k ones
• f[i][j][k] stores the maximum number of strings that can be selected

For each string, the algorithm counts its zeros and ones, then decides whether to include it or not by comparing the value of including it versus excluding it, ensuring the constraints on zeros and ones are satisfied.

Intuition

This problem is essentially a variant of the classic 0/1 knapsack problem, but with two constraints instead of one. In the traditional knapsack, we have items with weights and values, and we want to maximize value while staying within a weight limit. Here, we want to maximize the number of items (strings) selected while staying within two limits: the number of zeros and the number of ones.

The key insight is that for each string, we face a binary decision: either include it in our subset or don't. This "take it or leave it" nature immediately suggests dynamic programming as a solution approach.

Why can't we use a greedy approach? We might think to select strings with the fewest total characters first, or those with the best ratio of characters to constraints. However, this fails because the optimal solution depends on the combination of strings selected. A string that seems "expensive" (uses many 0s or 1s) might actually be part of the optimal solution if other selected strings complement it well by using mostly the other type of character.

The natural state representation emerges when we think about what information we need to make decisions:

1. Which strings we've already considered (position in the array)
2. How many zeros we've used so far (or have remaining)
3. How many ones we've used so far (or have remaining)

This leads us to define f[i][j][k] as the maximum number of strings we can select from the first i strings using at most j zeros and k ones.

The recurrence relation follows naturally: for each string, we can either:

• Skip it: f[i][j][k] = f[i-1][j][k]
• Take it (if we have enough capacity): f[i][j][k] = f[i-1][j-a][k-b] + 1 where a and b are the counts of zeros and ones in the current string

We choose the maximum of these two options, building up our solution from smaller subproblems to larger ones until we reach f[sz][m][n], which gives us the answer.

Solution Approach

The solution implements a 3D dynamic programming approach to solve this knapsack-like problem with two constraints.

Data Structure Setup: We create a 3D DP table f with dimensions (sz + 1) × (m + 1) × (n + 1) where:

• First dimension: represents considering strings from index 0 to i
• Second dimension: represents using at most j zeros
• Third dimension: represents using at most k ones

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

The table is initialized with all zeros, which represents the base case: when we have no strings to consider, the maximum subset size is 0.

Main Algorithm: We iterate through each string in the array using enumerate(strs, 1) to start indexing from 1 (this aligns with our DP table indexing):

1. Count characters in current string:

   a, b = s.count("0"), s.count("1")

   For each string, we first count how many zeros (a) and ones (b) it contains.

2. Fill the DP table: For each possible capacity of zeros j (from 0 to m) and ones k (from 0 to n):

   f[i][j][k] = f[i - 1][j][k]  # Don't take current string

   First, we assume we don't take the current string, inheriting the value from the previous state.

   if j >= a and k >= b:
       f[i][j][k] = max(f[i][j][k], f[i - 1][j - a][k - b] + 1)

   If we have enough capacity (j ≥ a zeros and k ≥ b ones), we consider taking the string. We compare:

   • Not taking it: f[i - 1][j][k]
   • Taking it: f[i - 1][j - a][k - b] + 1 (previous state with reduced capacity plus one string)

   We keep the maximum of these two options.

State Transition: The recurrence relation can be expressed as:

• f[i][j][k] = f[i-1][j][k] if we can't afford the current string (j < a or k < b)
• f[i][j][k] = max(f[i-1][j][k], f[i-1][j-a][k-b] + 1) if we can afford it

Final Result: After processing all strings, f[sz][m][n] contains the maximum number of strings we can select using at most m zeros and n ones.

The time complexity is O(len(strs) × m × n) as we fill a 3D table, and the space complexity is also O(len(strs) × m × n) for storing the DP table.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input: strs = ["10", "0", "1"], m = 1 (max zeros), n = 1 (max ones)

First, let's count zeros and ones in each string:

• "10": 1 zero, 1 one
• "0": 1 zero, 0 ones
• "1": 0 zeros, 1 one

We create a 3D DP table f[4][2][2] (dimensions: 4×2×2) initialized with zeros.

Initial state: f[0][j][k] = 0 for all j, k (no strings considered = 0 selected)

Processing string 1: "10" (1 zero, 1 one)

For each capacity combination (j zeros, k ones):

• f[1][0][0] = f[0][0][0] = 0 (can't take "10", need 1 zero and 1 one)
• f[1][0][1] = f[0][0][1] = 0 (can't take "10", need 1 zero)
• f[1][1][0] = f[0][1][0] = 0 (can't take "10", need 1 one)
• f[1][1][1] = max(f[0][1][1], f[0][0][0] + 1) = max(0, 0 + 1) = 1 (can take "10")

Processing string 2: "0" (1 zero, 0 ones)

• f[2][0][0] = f[1][0][0] = 0 (can't take "0", need 1 zero)
• f[2][0][1] = f[1][0][1] = 0 (can't take "0", need 1 zero)
• f[2][1][0] = max(f[1][1][0], f[1][0][0] + 1) = max(0, 0 + 1) = 1 (can take "0")
• f[2][1][1] = max(f[1][1][1], f[1][0][1] + 1) = max(1, 0 + 1) = 1 (take either "10" or "0")

Processing string 3: "1" (0 zeros, 1 one)

• f[3][0][0] = f[2][0][0] = 0 (can't take "1", need 1 one)
• f[3][0][1] = max(f[2][0][1], f[2][0][0] + 1) = max(0, 0 + 1) = 1 (can take "1")
• f[3][1][0] = max(f[2][1][0], f[2][1][0] + 1) = 1 (can't take "1", need 1 one)
• f[3][1][1] = max(f[2][1][1], f[2][1][0] + 1) = max(1, 1 + 1) = 2 (take "0" and "1")

Final answer: f[3][1][1] = 2

The optimal selection is {"0", "1"} which uses exactly 1 zero and 1 one, giving us 2 strings total.

This example demonstrates how the DP table builds up the solution by considering each string and tracking the maximum number of strings we can select for each combination of zero and one capacities.

Solution Implementation

Time and Space Complexity

Time Complexity: O(sz * m * n) where sz is the length of the input array strs, m is the maximum number of 0's allowed, and n is the maximum number of 1's allowed.

The algorithm uses three nested loops:

• The outer loop iterates through all strings in strs (sz iterations)
• The middle loop iterates from 0 to m (m + 1 iterations)
• The inner loop iterates from 0 to n (n + 1 iterations)

Additionally, for each string, we count the number of 0's and 1's using s.count(), which takes O(len(s)) time. If we denote the average length of strings as L, this adds O(sz * L) to the complexity. However, since the triple nested loop dominates, the overall time complexity remains O(sz * m * n) when L is relatively small compared to m * n.

Space Complexity: O(sz * m * n)

The algorithm creates a 3D DP array f with dimensions (sz + 1) * (m + 1) * (n + 1). This array stores the maximum number of strings that can be formed for each combination of:

• First i strings considered (0 to sz)
• Using at most j zeros (0 to m)
• Using at most k ones (0 to n)

The total space required is (sz + 1) * (m + 1) * (n + 1), which simplifies to O(sz * m * n).

Common Pitfalls

1. Memory Inefficiency in Space Complexity

The Pitfall: The current solution uses a 3D DP table with dimensions (len(strs) + 1) × (m + 1) × (n + 1), which can consume excessive memory when dealing with large inputs. For instance, if you have 600 strings with m=100 and n=100, you'd need to allocate space for 600 × 101 × 101 ≈ 6 million integers, which could cause memory issues or TLE in competitive programming.

Why This Happens: The 3D approach stores all intermediate states for every string, but we only ever need the previous string's states to compute the current string's states. This makes most of the stored data unnecessary.

The Solution - Space Optimization to 2D: Since we only need the previous row (i-1) to compute the current row (i), we can reduce the space complexity from O(len(strs) × m × n) to O(m × n) by using a 2D DP table and updating it in reverse order:

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # Use 2D DP instead of 3D
        dp = [[0] * (n + 1) for _ in range(m + 1)]
      
        for s in strs:
            zeros = s.count('0')
            ones = s.count('1')
          
            # Iterate in reverse to avoid using updated values
            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]

Key Insight: By iterating backwards (from m to zeros and n to ones), we ensure that when we update dp[i][j], we're using the values from the "previous iteration" (before including the current string), not the updated values from the current iteration.

2. Incorrect Loop Order Leading to Wrong Results

The Pitfall: When optimizing to 2D DP, a common mistake is iterating in the forward direction:

# WRONG - This will give incorrect results!
for i in range(zeros, m + 1):  # Forward iteration
    for j in range(ones, n + 1):
        dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

Why This Fails: Forward iteration causes us to use already-updated values from the current string when calculating new states. This effectively allows us to use the same string multiple times, violating the constraint that each string can only be used once.

Example of the Bug: Consider string "01" (1 zero, 1 one) with m=2, n=2:

• Forward iteration: dp[1][1] gets updated to 1
• Then dp[2][2] = max(0, dp[1][1] + 1) = 2 (using the same string twice!)
• Backward iteration correctly gives dp[2][2] = 1

3. Off-by-One Errors in Boundary Conditions

The Pitfall: Incorrectly setting loop boundaries, especially when checking if we have enough capacity:

# WRONG - May miss valid combinations
if zeros_limit > zeros_count and ones_limit > ones_count:  # Should be >=

The Solution: Always use >= when checking capacity constraints, as we need to include the case where we have exactly enough zeros/ones:

if zeros_limit >= zeros_count and ones_limit >= ones_count:
    # Include the string

This ensures we don't miss valid selections where the string exactly uses all available zeros or ones.