Each binary string has a “cost”: how many 0s and how many 1s it consumes. We want the maximum number of strings we can pick without spending more than m zeros and n ones.
Think of every string as an item with a 2-dimensional cost.
Unlike ordinary knapsack, we do not maximize money or value. Every chosen string is worth exactly 1, so our goal is simply to maximize how many strings are selected.
Let:
At each string, there are only two possibilities:
SKIP → move to dfs(i+1, z, o)
TAKE → if it fits, get 1 + dfs(...remaining capacity...)
Example: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Pure recursion can reach the same state through different take/skip histories. Once we have solved (i, z, o), solving it again is wasted work.
Memoization stores the result for that state and reuses it immediately.
So the time complexity is O(L × m × n + total characters), where L is the number of strings.
Watch repeated subproblems become cache hits during the demo.
class Solution:
def findMaxForm(self, strs, m, n):
counts = []
for s in strs:
zeros = s.count("0")
ones = s.count("1")
counts.append((zeros, ones))
memo = {}
def dfs(i, zeros_left, ones_left):
# Base case: no strings left
if i == len(strs):
return 0
state = (i, zeros_left, ones_left)
# Reuse an already solved state
if state in memo:
return memo[state]
z, o = counts[i]
# Option 1: skip current string
skip = dfs(i + 1, zeros_left, ones_left)
# Option 2: take current string, if it fits
take = 0
if z <= zeros_left and o <= ones_left:
take = 1 + dfs(
i + 1,
zeros_left - z,
ones_left - o
)
memo[state] = max(skip, take)
return memo[state]
return dfs(0, m, n)The second branch is allowed only when the current string fits inside the remaining zero/one budget.
The important observation is not “count the zeros and ones.” The key is recognizing that each item consumes two limited resources. That turns the problem into a two-capacity 0/1 knapsack.
Once the state is written as (index, zerosLeft, onesLeft), recursion becomes natural, and memoization removes duplicate work.