LeetCode Challenge Day 57 — 474. Ones and Zeroes

Hey folks 👋

This is Day 57 of my LeetCode streak 🚀
Today’s problem is 474. Ones and Zeroes — a medium-level dynamic programming problem that generalizes the classic 0/1 knapsack into two dimensions — zeros and ones.

The goal is to pick the largest subset of strings such that the total number of zeros ≤ m and ones ≤ n.

📌 Problem Statement

You are given an array of binary strings strs and two integers m and n.
Return the size of the largest subset of strs such that there are at most m zeros and at most n ones in the subset.

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4

Explanation: The largest subset with at most 5 zeros and 3 ones is 0.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2

Explanation: The largest subset is 1.

💡 Intuition

This problem resembles a knapsack problem — each binary string is like an “item” with a cost in two dimensions:

• Cost in zeros
• Cost in ones

You have limited capacities (m zeros and n ones).
Your task is to choose as many items (strings) as possible without exceeding these capacities.

🔑 Approach

1. Define a DP table:
   Let dp[i][j] represent the maximum number of strings you can form with at most i zeros and j ones.

2. Process each string:

   • Count the number of zeros and ones in the string.
   • Traverse the DP table in reverse order (from m to zeros, n to ones) to ensure each string is only used once.

3. Transition:

4. Result:
   The answer is stored in dp[m][n].

⏱️ Complexity Analysis

• Time Complexity:
  ( O(L \times m \times n) ), where L = number of strings.
  Each string updates the entire DP table once.

• Space Complexity:
  ( O(m \times n) ) — using a 2D array for DP.

🧑‍💻 Code (JavaScript)

/**
* @param {string[]} strs
* @param {number} m
* @param {number} n
* @return {number}
*/
var findMaxForm = function(strs, m, n) {
 // dp[i][j] = max number of strings we can form with at most i zeros and j ones
 const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
 
 for (const s of strs) {
     // count zeros and ones in current string
     let zeros = 0, ones = 0;
     for (let ch of s) {
         if (ch === '0') zeros++;
         else ones++;
     }
     // update dp in reverse to avoid reuse of the same string
     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];
};

🧩 Example Walkthrough

Input: strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

Process:

• "10" → (1 zero, 1 one)

• "0001" → (3 zeros, 1 one)

• "111001" → (2 zeros, 4 ones)

• "1" → (0 zeros, 1 one)

• "0" → (1 zero, 0 ones)

You can pick 0 → total = 4 strings.

Output: 4

🎯 Reflection

This problem beautifully illustrates how multi-dimensional constraints extend classical DP problems. By adapting knapsack logic to track both zeros and ones, we efficiently determine the largest subset size possible.

That’s it for Day 57 of my LeetCode challenge 💪 Keep learning, keep optimizing — one DP state at a time ⚡

Happy Coding 👨‍💻