Log inSign up
mediumLeetCodeNot Started

Ones and Zeroes

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

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 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

### Example 1 - Input: strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 - Output: 4 - Explanation: The largest subset with at most 5 zeroes and 3 ones is {"10", "0001", "1", "0"} (4 strings). It contains 5 zeroes and 3 ones.

### Example 2 - Input: strs = ["10", "0", "1"], m = 1, n = 1 - Output: 2 - Explanation: You could select {"0", "1"} (size 2).

Constraints:

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] consists only of digits 0 and 1
  • 1 <= m, n <= 100

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Extend single-budget 0/1 knapsack to multi-dimensional budgets.
  • Implement double backward traversal in 2D array.
  • Maximize subset cardinality under linear constraints.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Subset selection with two simultaneous capacity constraints.
  • Binary strings with counts of 0s and 1s.

Algorithmic Decision Tree:

  • Count 0s and 1s for each string.
  • Double nested backward loops for space optimization.

Connected Patterns:

Coin ChangeSubset Sum0/1 Knapsack

1. Recursive Inclusion / Exclusion

Intuition

Recursively decide whether to include or exclude each string while checking budget constraints.

Algorithm

  1. Define solve(idx, remM, remN).
  2. If idx == S, return 0.
  3. Option 1: Exclude string: solve(idx + 1, remM, remN).
  4. Option 2: Include string (if count0 <= remM && count1 <= remN): 1 + solve(idx + 1, remM - count0, remN - count1).
  5. Return max(Option 1, Option 2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 int solve(int idx, int m, int n, const vector<pair<int, int>>& items) {
10 if (idx == items.size()) return 0;
11 int notTake = solve(idx + 1, m, n, items);
12 int take = 0;
13 if (m >= items[idx].first && n >= items[idx].second) {
14 take = 1 + solve(idx + 1, m - items[idx].first, n - items[idx].second, items);
15 }
16 return max(notTake, take);
17 }
18public:
19 int findMaxForm(vector<string>& strs, int m, int n) {
20 vector<pair<int, int>> items;
21 for (const string& s : strs) {
22 int z = 0, o = 0;
23 for (char c : s) { if (c == '0') z++; else o++; }
24 items.push_back({z, o});
25 }
26 return solve(0, m, n, items);
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<string> strs = {"10", "0001", "111001", "1", "0"};
33 cout << "Max Form: " << sol.findMaxForm(strs, 5, 3) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(2^S)
  • Space complexity: O(S) call stack

2. Memoized 3D DP

Intuition

Memoize states (idx, remM, remN) using a 3D table of size S x (m+1) x (n+1).

Algorithm

  1. Initialize 3D array memo[S][m+1][n+1] with -1.
  2. In solve(idx, remM, remN): return cached result if != -1.
  3. Compute max of include and exclude.
  4. Save and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 int solve(int idx, int m, int n, const vector<pair<int, int>>& items, vector<vector<vector<int>>>& memo) {
10 if (idx == items.size()) return 0;
11 if (memo[idx][m][n] != -1) return memo[idx][m][n];
12
13 int notTake = solve(idx + 1, m, n, items, memo);
14 int take = 0;
15 if (m >= items[idx].first && n >= items[idx].second) {
16 take = 1 + solve(idx + 1, m - items[idx].first, n - items[idx].second, items, memo);
17 }
18
19 return memo[idx][m][n] = max(notTake, take);
20 }
21public:
22 int findMaxForm(vector<string>& strs, int m, int n) {
23 vector<pair<int, int>> items;
24 for (const string& s : strs) {
25 int z = 0, o = 0;
26 for (char c : s) { if (c == '0') z++; else o++; }
27 items.push_back({z, o});
28 }
29 int S = items.size();
30 vector<vector<vector<int>>> memo(S, vector<vector<int>>(m + 1, vector<int>(n + 1, -1)));
31 return solve(0, m, n, items, memo);
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<string> strs = {"10", "0001", "111001", "1", "0"};
38 cout << "Max Form: " << sol.findMaxForm(strs, 5, 3) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(S * m * n)
  • Space complexity: O(S * m * n)

3. Space-Optimized 2D Array Tabulation (O(m * n) Space)

Intuition

Use a 2D array dp[m + 1][n + 1] traversed in reverse along both dimensions for each string.

Algorithm

  1. Initialize 2D array dp[m + 1][n + 1] with 0.
  2. For each string in strs:
  3. Count zeroes z and ones o.
  4. For i from m down to z:
  5. For j from n down to o:
  6. dp[i][j] = max(dp[i][j], 1 + dp[i - z][j - o]).
  7. Return dp[m][n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int findMaxForm(vector<string>& strs, int m, int n) {
11 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
12
13 for (const string& s : strs) {
14 int z = 0, o = 0;
15 for (char c : s) {
16 if (c == '0') z++;
17 else o++;
18 }
19
20 for (int i = m; i >= z; --i) {
21 for (int j = n; j >= o; --j) {
22 dp[i][j] = max(dp[i][j], 1 + dp[i - z][j - o]);
23 }
24 }
25 }
26
27 return dp[m][n];
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<string> strs = {"10", "0001", "111001", "1", "0"};
34 cout << "Max Form: " << sol.findMaxForm(strs, 5, 3) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(S * m * n)
  • Space complexity: O(m * n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive SearchO(2^S)O(S)Exhaustive branching over inclusion/exclusion.Overlapping subsets
2.Memoized 3D DPO(S * m * n)O(S * m * n)Cache states in 3D memo table.3D table allocation
3.Space-Optimized 2D Array TabulationOptimalO(S * m * n)O(m * n)Double reverse loop in 2D array.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating forward in either of the two loops: Reuses strings multiple times.

Pitfall 2:

Counting characters repeatedly inside the inner loops instead of precomputing.

Crucial Edge Cases to Validate:

  • No string can fit in budget (e.g. all have > m zeroes or > n ones): Returns 0.
  • Single character strings 0 and 1: Handled smoothly with count (1, 0) and (0, 1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State clearly: 'This is a multi-dimensional (2-constraint) 0/1 Knapsack problem where each string costs (zeros, ones) and yields value 1.' Interviewers love immediate problem classification.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must both loops (i from m down to z, and j from n down to o) run in REVERSE?

Back to DSA Sheet