AlgoMaster Logo

Ones and Zeroes

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

This problem asks us to pick as many strings as possible from the given array, but with a budget constraint: the total number of zeroes across all chosen strings cannot exceed m, and the total number of ones cannot exceed n.

This is a variant of the 0/1 Knapsack problem. In the traditional knapsack, there is one capacity constraint (weight). Here there are two capacity constraints (zeroes and ones). For each string, we decide to either include it or skip it, and including it spends some zeroes and some ones from the budget. We want to maximize the count of chosen strings while staying within both budgets at the same time.

Key Constraints:

  • 1 <= strs.length <= 600 → With up to 600 strings and two budget dimensions of size 100, a DP keyed on (string index, zeroes left, ones left) has 600 x 101 x 101 ≈ 6.1 million states, well within time limits. An exponential search over all subsets is ruled out at this size.
  • 1 <= m, n <= 100 → The two budget dimensions are small enough to hold a 101 x 101 table in memory, which is what makes the optimized bottom-up solution practical.

Approach 1: Brute Force (Recursion)

Intuition

For each string we have a binary decision: include it or skip it. Trying every combination of these decisions and keeping the largest valid subset gives the answer directly.

This is a recursive exploration of all 2^L subsets, where L is the number of strings. At each string we look at its zero and one cost. We always have the option to skip it. We can also include it when both its zero cost and its one cost fit in the remaining budget, in which case we add 1 and recurse with the reduced budget. The result for a string is the better of the two options.

With up to 600 strings, exploring 2^600 subsets is far too slow, but this recursion defines the choices and the optimal substructure that the next two approaches build on.

Algorithm

  1. Precompute the number of zeroes and ones for each string in strs.
  2. Define a recursive function solve(index, zeroesLeft, onesLeft) that returns the maximum subset size starting from index with the given remaining budget.
  3. Base case: if index == strs.length, return 0 (no more strings to consider).
  4. Always try skipping the current string: skip = solve(index + 1, zeroesLeft, onesLeft).
  5. If including the current string fits within the budget (zeroes <= zeroesLeft and ones <= onesLeft), try including it: include = 1 + solve(index + 1, zeroesLeft - zeroes, onesLeft - ones).
  6. Return the maximum of skip and include.

Visualization and Code

Loading animation...

This approach is correct, but the exponential time makes it impractical for L up to 600. The recursion repeats work because the same (index, zeroesLeft, onesLeft) state gets recomputed along many different paths. Caching each state's result removes that repetition.

Approach 2: Memoization (Top-Down DP)

Intuition

The brute force recursion recomputes the same states repeatedly. Including string 0 and skipping string 1 might reach state (2, 3, 2). Skipping string 0 and including string 1 reaches the same state whenever those two strings spend the same budget. Both paths then re-explore the identical subtree below that state.

Memoization stores the result of each unique (index, zeroesLeft, onesLeft) state in a 3D array. Before computing a state we check whether it is already solved, and if so return the stored result. This caps the total work at the number of distinct states.

The number of unique states is bounded by L x (m+1) x (n+1), which for the maximum inputs is 600 x 101 x 101 ≈ 6.1 million.

Algorithm

  1. Precompute zeroes and ones for each string.
  2. Create a 3D memo array of size [L][m+1][n+1] initialized to -1.
  3. Use the same recursive structure as Approach 1, but before computing a state, check if memo[index][zeroesLeft][onesLeft] is already computed.
  4. Store results in the memo array before returning.

Visualization and Code

Loading animation...

Approach 3: Bottom-Up DP (2D Table)

Intuition

This is the standard 0/1 Knapsack optimization applied to two budget dimensions. Instead of a 3D table indexed by (string index, zeroes budget, ones budget), we collapse the string dimension and keep a 2D table dp[i][j], the maximum number of strings selectable using at most i zeroes and j ones across all strings processed so far.

When processing a string we iterate the budgets in reverse, from high to low. This is what keeps each string usable at most once. The update dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1) reads dp[i-z][j-o], a cell with smaller budgets. Iterating high to low means that smaller-budget cell still holds the value from before the current string was processed, so the current string is added on top of subsets that do not already contain it. Iterating low to high would read a cell that was already updated with the current string in this same pass, letting the string be counted more than once.

Algorithm

  1. Create a 2D array dp[m+1][n+1] initialized to 0. Here dp[i][j] means "the maximum subset size achievable with at most i zeroes and j ones."
  2. For each string in strs:
    • Count its zeroes (z) and ones (o).
    • Iterate i from m down to z, and j from n down to o.
    • Update: dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1).
  3. Return dp[m][n].

Visualization and Code

Loading animation...