Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumknapsack-subset-dp

Ones and Zeroes

Problem (restated)

Binary strings strs; budgets m zeros and n ones. Largest subset of strings formable without exceeding budgets.

Intuition

Each string is an item costing (zeros, ones) with value 1. Classic 0/1 knapsack in 2D capacity.

Approaches

2D 0/1 knapsack

Tested only

Time O(L·m·n)Space O(m·n)

Idea. dp[i][j] = max strings with ≤i zeros and ≤j ones. Iterate items reverse on capacities.

Walkthrough. strs=[“10”,“0001”,“111001”,“1”,“0”], m=5,n=3 → 4.

Trade-offs. Forward loops would reuse the same string; reverse enforces 0/1.

Solution

export function findMaxForm(strs: string[], m: number, n: number): number {
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (const s of strs) {
    let zeros = 0, ones = 0;
    for (const c of s) if (c === "0") zeros++; else ones++;
    for (let i = m; i >= zeros; i--) {
      for (let j = n; j >= ones; j--) {
        dp[i]![j] = Math.max(dp[i]![j]!, dp[i - zeros]![j - ones]! + 1);
      }
    }
  }
  return dp[m]![n]!;
}

export function findMaxForm(strs: string[], m: number, n: number): number {
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (const s of strs) {
    let zeros = 0, ones = 0;
    for (const c of s) if (c === "0") zeros++; else ones++;
    for (let i = m; i >= zeros; i--) {
      for (let j = n; j >= ones; j--) {
        dp[i]![j] = Math.max(dp[i]![j]!, dp[i - zeros]![j - ones]! + 1);
      }
    }
  }
  return dp[m]![n]!;
}

Template connection

0/1 knapsack with multi-dimensional capacity.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?