229. Ones and Zeroes
🔗 LeetCode Problem: 474. Ones and Zeroes
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, String, DP - Subsequences, Multi-Dimensional Knapsack
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 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
Example 2:
Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.
Constraints:
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] consists only of digits '0' and '1'.
- 1 <= m, n <= 100
🌳 Visual Understanding - Using strs = ["10","0001","111001","1","0"], m = 5, n = 3
The Problem We're Solving:
Given: strs = ["10", "0001", "111001", "1", "0"]
m = 5 (max 0's allowed)
n = 3 (max 1's allowed)
Goal: Find largest subset where total 0's ≤ 5 and total 1's ≤ 3
Count 0's and 1's in each string:
"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
Question: Which strings can we select to maximize count
while staying within budget of 5 zeros and 3 ones? 🤔
Finding the Largest Subset:
Budget: 5 zeros, 3 ones
Try selecting strings:
Option 1: ["10", "0001", "1", "0"]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"10" → 1 zero, 1 one | Total: 1 zero, 1 one
"0001" → 3 zeros, 1 one | Total: 4 zeros, 2 ones
"1" → 0 zeros, 1 one | Total: 4 zeros, 3 ones
"0" → 1 zero, 0 ones | Total: 5 zeros, 3 ones ✓
Count: 4 strings ✓
Within budget: 5 zeros ≤ 5 ✓, 3 ones ≤ 3 ✓
Option 2: ["10", "0001", "111001"]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"10" → 1 zero, 1 one | Total: 1 zero, 1 one
"0001" → 3 zeros, 1 one | Total: 4 zeros, 2 ones
"111001" → 2 zeros, 4 ones | Total: 6 zeros, 6 ones ✗
Count: 3 strings
Exceeds budget: 6 zeros > 5 ✗, 6 ones > 3 ✗
INVALID!
Option 3: ["0001", "1", "0"]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"0001" → 3 zeros, 1 one | Total: 3 zeros, 1 one
"1" → 0 zeros, 1 one | Total: 3 zeros, 2 ones
"0" → 1 zero, 0 ones | Total: 4 zeros, 2 ones ✓
Count: 3 strings
Within budget but smaller than option 1!
Maximum: 4 strings from option 1
Answer: 4 ✓
Why This Is Tricky - Two Constraints:
REGULAR 0/1 KNAPSACK:
One constraint: weight ≤ W
Example: Can carry weight ≤ 50kg
THIS PROBLEM:
Two constraints:
zeros ≤ m
ones ≤ n
Example: Can use ≤ 5 zeros AND ≤ 3 ones
This is MULTI-DIMENSIONAL Knapsack! 🔑
Think of it like packing with TWO limits:
- Bag can hold max 5kg of apples
- Bag can hold max 3kg of oranges
- Each item has both apple and orange weight
- Maximize number of items packed!
Visual Example with Budget Tracking:
Budget: 5 zeros, 3 ones
String: "10" (1 zero, 1 one)
Include? Budget: (5-1, 3-1) = (4, 2) remaining ✓
String: "0001" (3 zeros, 1 one)
Include? Budget: (4-3, 2-1) = (1, 1) remaining ✓
String: "111001" (2 zeros, 4 ones)
Include? Budget: (1-2, 1-4) = (-1, -3) ✗
Can't afford 4 ones! Skip!
String: "1" (0 zeros, 1 one)
Include? Budget: (1-0, 1-1) = (1, 0) remaining ✓
String: "0" (1 zero, 0 ones)
Include? Budget: (1-1, 0-0) = (0, 0) remaining ✓
Selected: 4 strings ["10", "0001", "1", "0"]
Budget used: exactly (5, 3) - perfect!
🧠 The AHA Moment - Why This Problem Is Special
What Makes This Different?
REGULAR 0/1 KNAPSACK:
Items: weights and values
Constraint: weight ≤ W
Maximize: value
dp[weight] = max value at weight
THIS PROBLEM (2D Knapsack):
Items: zero_count and one_count
Constraints: zeros ≤ m AND ones ≤ n
Maximize: number of items
dp[zeros][ones] = max items at (zeros, ones)
Key difference: TWO dimensions of constraints! 🎯
The Key Insight - Track Both Dimensions:
For each string, it costs:
- Some number of 0's
- Some number of 1's
We have budget:
- m 0's total
- n 1's total
Decision for each string:
Include? → Spend its 0's and 1's, get +1 to count
Skip? → Keep budget, don't increase count
Need to track BOTH budgets simultaneously!
dp[i][j] = "maximum strings we can select
using at most i zeros and j ones"
Building Intuition:
Think of it like shopping with two currencies:
Budget: 5 gold coins, 3 silver coins
Items in store:
Item A: costs 1 gold, 1 silver → value = 1 item
Item B: costs 3 gold, 1 silver → value = 1 item
Item C: costs 2 gold, 4 silver → TOO EXPENSIVE (need 4 silver!)
Item D: costs 0 gold, 1 silver → value = 1 item
Item E: costs 1 gold, 0 silver → value = 1 item
Maximize number of items bought within budget!
Same structure as our problem:
Gold = zeros
Silver = ones
Value of each item = 1 (we count items, not maximize value)
🔴 Approach 1: Brute Force (Try All Subsets)
📐 Function Definition
Function Signature:
int findMaxForm(String[] strs, int m, int n)
What it represents:
Input Parameter strs:
- Array of binary strings
- Each string used 0 or 1 times
- Example: ["10", "0001", "111001", "1", "0"]
Input Parameters m and n:
- m = max zeros allowed
- n = max ones allowed
- Example: m = 5, n = 3
Return Value (int): - Maximum number of strings we can select - While staying within (m, n) budget - Example: 4
Purpose: - Count 0's and 1's in each string - Try all possible subsets (2^k combinations) - For each subset, check if within budget - Return maximum count of valid subsets
Key Understanding:
For each string:
Include? → Cost: (zeros, ones), Gain: +1 to count
Skip? → Cost: (0, 0), Gain: 0 to count
Try ALL combinations, pick best!
💡 Intuition
The simplest idea: Try all possible subsets!
Think of it like choosing items to pack:
Strings: ["10", "0001", "111001", "1", "0"]
Budget: 5 zeros, 3 ones
Decision tree:
Start (5,3)
/ \
Include "10" Skip "10"
(4,2) (5,3)
/ \ / \
Include Skip Include Skip
"0001" "0001" "0001" "0001"
(1,1) (4,2) (2,2) (5,3)
... ... ... ...
At each string:
- Include → reduce budget, count++
- Skip → keep budget, count stays same
Try ALL 2^k paths! Track maximum count! ✓
📝 Implementation
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
return helper(strs, 0, m, n);
}
private int helper(String[] strs, int index, int m, int n) {
// Base case: no more strings
if (index >= strs.length) {
return 0;
}
// Count 0's and 1's in current string
int zeros = 0, ones = 0;
for (char c : strs[index].toCharArray()) {
if (c == '0') zeros++;
else ones++;
}
// Choice 1: Skip current string
int skip = helper(strs, index + 1, m, n);
// Choice 2: Include current string (if we can afford it)
int include = 0;
if (m >= zeros && n >= ones) {
include = 1 + helper(strs, index + 1, m - zeros, n - ones);
}
return Math.max(skip, include);
}
}
🔍 Detailed Dry Run: strs = ["10","0","1"], m = 1, n = 1
Strings with counts:
"10" → 1 zero, 1 one
"0" → 1 zero, 0 ones
"1" → 0 zeros, 1 one
Budget: 1 zero, 1 one
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RECURSIVE TREE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(strs, 0, 1, 1) - Process "10"
│
├─ Skip "10": helper(strs, 1, 1, 1)
│ │
│ ├─ Skip "0": helper(strs, 2, 1, 1)
│ │ │
│ │ ├─ Skip "1": helper(strs, 3, 1, 1)
│ │ │ return 0 (no more strings)
│ │ │
│ │ └─ Include "1": helper(strs, 3, 1, 0)
│ │ return 0 + 1 = 1 ✓
│ │
│ │ max(0, 1) = 1
│ │ return 1
│ │
│ └─ Include "0": helper(strs, 2, 0, 1)
│ │
│ ├─ Skip "1": helper(strs, 3, 0, 1)
│ │ return 0
│ │
│ └─ Include "1": helper(strs, 3, 0, 0)
│ return 0 + 1 = 1 ✓
│
│ max(0, 1) = 1
│ return 1 + 1 = 2 ✓
│
│ max(1, 2) = 2
│ return 2
│
└─ Include "10": helper(strs, 1, 0, 0)
│
├─ Skip "0": helper(strs, 2, 0, 0)
│ │
│ └─ Skip "1": helper(strs, 3, 0, 0)
│ return 0
│
│ return 0
│
└─ Include "0": Can't afford! (need 1 zero, have 0)
return 1 + 0 = 1
max(2, 1) = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Best selection: ["0", "1"]
"0" costs (1, 0)
"1" costs (0, 1)
Total: (1, 1) = exactly the budget!
Count: 2 strings ✓
Why This Is Slow:
Decision tree has 2^k paths (k = length of strs)
For each string: 2 choices (include or skip)
Total combinations: 2^k
Example:
k = 3: 2^3 = 8 paths
k = 10: 2^10 = 1,024 paths
k = 20: 2^20 = 1,048,576 paths
k = 600: 2^600 = astronomical!
Many paths explore same (index, m, n) states!
This is why brute force is TOO SLOW! ❌
📊 Complexity Analysis
Time Complexity: O(2^k)
k = length of strs array
At each string: 2 choices
Total paths: 2^k
For k = 600: completely impractical!
WAY TOO SLOW! ❌
Space Complexity: O(k)
Recursion stack depth
In worst case, depth = k
Why This Is Slow:
❌ Tries every possible subset
❌ Repeats same (index, m, n) states
❌ Exponential time complexity
✅ But correct and easy to understand!
We need to CACHE the results! → Memoization!
🟡 Approach 2: Memoization (Top-Down DP)
📐 Function Definition
Function Signature:
int findMaxForm(String[] strs, int m, int n)
What it represents:
Variables we track:
- memo[index][zeros][ones] = Max strings using strs[index..k-1] with (zeros, ones) budget
- If computed, reuse it!
- If not computed, compute and cache it!
Purpose: - Same recursive logic as brute force - But CACHE results to avoid recomputation - Each (index, m, n) state solved only ONCE!
Key Understanding:
Brute force calls helper(2, 4, 3) many times
Memoization calls helper(2, 4, 3) ONCE, caches result
Example:
First time helper(2, 4, 3) called:
- Compute answer
- Store in memo[2][4][3]
Next time helper(2, 4, 3) called:
- Check memo[2][4][3]
- Found! Return immediately
- No recomputation! ✓
This saves MASSIVE amounts of work!
💡 Intuition
The smart idea: Remember what we've already computed!
Think of it like a 3D lookup table:
WITHOUT memoization (brute force):
Question: "Max strings from index 2 with (4,3) budget?"
You: *explore all possibilities*
Later, same question again!
You: *explore all possibilities AGAIN* ❌
WITH memoization:
Question: "Max strings from index 2 with (4,3) budget?"
You: *explore all possibilities*
You: *write in table: [2][4][3] = 3*
Later, same question again!
You: *check table[2][4][3]*
You: "It's 3!" ✓
You: *instant answer!*
The table is the memo array!
📝 Implementation
class Solution {
private int[][][] memo;
public int findMaxForm(String[] strs, int m, int n) {
memo = new int[strs.length][m + 1][n + 1];
// Initialize with -1 (not computed)
for (int i = 0; i < strs.length; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
memo[i][j][k] = -1;
}
}
}
return helper(strs, 0, m, n);
}
private int helper(String[] strs, int index, int m, int n) {
// Base case: no more strings
if (index >= strs.length) {
return 0;
}
// Check memo (our lookup table!)
if (memo[index][m][n] != -1) {
return memo[index][m][n];
}
// Count 0's and 1's in current string
int zeros = 0, ones = 0;
for (char c : strs[index].toCharArray()) {
if (c == '0') zeros++;
else ones++;
}
// Choice 1: Skip current string
int skip = helper(strs, index + 1, m, n);
// Choice 2: Include current string (if we can afford it)
int include = 0;
if (m >= zeros && n >= ones) {
include = 1 + helper(strs, index + 1, m - zeros, n - ones);
}
// Save to memo before returning!
memo[index][m][n] = Math.max(skip, include);
return memo[index][m][n];
}
}
🔍 Detailed Dry Run: strs = ["10","0","1"], m = 1, n = 1
Strings with counts:
"10" → 1 zero, 1 one
"0" → 1 zero, 0 ones
"1" → 0 zeros, 1 one
memo = int[3][2][2] (all -1 initially)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
CALL: helper(strs, 0, 1, 1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
index = 0, m = 1, n = 1
memo[0][1][1] = -1 (not computed)
String "10": 1 zero, 1 one
Skip "10":
┌─ CALL: helper(strs, 1, 1, 1)
│ index = 1, m = 1, n = 1
│ memo[1][1][1] = -1
│
│ String "0": 1 zero, 0 ones
│
│ Skip "0":
│ ┌─ CALL: helper(strs, 2, 1, 1)
│ │ index = 2, m = 1, n = 1
│ │ memo[2][1][1] = -1
│ │
│ │ String "1": 0 zeros, 1 one
│ │
│ │ Skip "1":
│ │ return 0 (index >= 3)
│ │
│ │ Include "1":
│ │ 1 + helper(strs, 3, 1, 0)
│ │ 1 + 0 = 1
│ │
│ │ max(0, 1) = 1
│ │ memo[2][1][1] = 1 ✓
│ └─ return 1
│
│ Include "0":
│ 1 + helper(strs, 2, 0, 1)
│ ┌─ CALL: helper(strs, 2, 0, 1)
│ │ memo[2][0][1] = -1
│ │
│ │ Skip "1":
│ │ return 0
│ │
│ │ Include "1":
│ │ 1 + helper(strs, 3, 0, 0)
│ │ 1 + 0 = 1
│ │
│ │ max(0, 1) = 1
│ │ memo[2][0][1] = 1 ✓
│ └─ return 1
│
│ 1 + 1 = 2
│
│ max(1, 2) = 2
│ memo[1][1][1] = 2 ✓
└─ return 2
Include "10":
1 + helper(strs, 1, 0, 0)
┌─ CALL: helper(strs, 1, 0, 0)
│ memo[1][0][0] = -1
│
│ Can't include "0" (need 1 zero, have 0)
│ Skip "0":
│ helper(strs, 2, 0, 0)
│ (Similar computation)
│ return 0
│
│ memo[1][0][0] = 0 ✓
└─ return 0
1 + 0 = 1
max(2, 1) = 2
memo[0][1][1] = 2 ✓
return 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL memo state (selected cells):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
memo[0][1][1] = 2
memo[1][1][1] = 2
memo[1][0][0] = 0
memo[2][1][1] = 1
memo[2][0][1] = 1
Each state computed ONCE and cached! ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why This Works:
KEY INSIGHT:
Each unique (index, m, n) state is solved ONCE
Result is cached in memo[index][m][n]
Future calls return cached result instantly
Comparison:
Brute force: Same state explored multiple times
Memoization: Same state computed ONCE, cached
This transforms exponential → polynomial time!
📊 Complexity Analysis
Time Complexity: O(k × m × n)
k = length of strs
m = max zeros
n = max ones
States: k × m × n
Each state computed ONCE
Work per state: O(L) where L = average string length
Total: O(k × m × n × L)
For k=600, m=100, n=100, L=100:
600 × 100 × 100 × 100 = 600,000,000 operations
Still manageable! Much better than 2^600!
Space Complexity: O(k × m × n)
Memo array: O(k × m × n)
Recursion stack: O(k)
Total: O(k × m × n)
🟢 Approach 3: Bottom-Up DP (Iterative 3D)
📐 Function Definition
Function Signature:
int findMaxForm(String[] strs, int m, int n)
What it represents:
DP Array:
- dp[i][j][k] = Max strings using first i strings with budget (j zeros, k ones)
- Build from dp[0][0][0] up to dp[len][m][n]
- Each value uses previous values!
Purpose: - Process strings one by one - For each string, for each budget (j, k) - Decide: include or skip - Use previously computed dp values!
Key Understanding:
Bottom-up builds from smallest to largest:
dp[0][j][k] = 0 (no strings, count = 0)
dp[i][j][k]: Max strings using first i strings with (j, k) budget
Option 1: Don't use string i-1 → dp[i-1][j][k]
Option 2: Use string i-1 → 1 + dp[i-1][j-zeros][k-ones]
Build up the solution incrementally!
💡 Intuition
The systematic idea: Build 3D table from bottom up!
Think of it like filling a 3D cube:
Dimensions:
- Axis 1: Strings (0 to k)
- Axis 2: Zeros budget (0 to m)
- Axis 3: Ones budget (0 to n)
Start with layer 0 (no strings): all zeros
Build layer 1 (first string)
Build layer 2 (first two strings)
...
Build layer k (all strings)
Each cell uses cells from previous layer!
📝 Implementation
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int k = strs.length;
// dp[i][j][k] = max strings using first i with (j,k) budget
int[][][] dp = new int[k + 1][m + 1][n + 1];
// Base case: 0 strings = 0 count (already initialized to 0)
// Process each string
for (int i = 1; i <= k; i++) {
// Count 0's and 1's in current string
int zeros = 0, ones = 0;
for (char c : strs[i - 1].toCharArray()) {
if (c == '0') zeros++;
else ones++;
}
// For each possible budget
for (int j = 0; j <= m; j++) {
for (int l = 0; l <= n; l++) {
// Option 1: Don't include string i-1
dp[i][j][l] = dp[i - 1][j][l];
// Option 2: Include string i-1 (if we can afford it)
if (j >= zeros && l >= ones) {
dp[i][j][l] = Math.max(
dp[i][j][l],
1 + dp[i - 1][j - zeros][l - ones]
);
}
}
}
}
return dp[k][m][n];
}
}
🔍 Detailed Dry Run: strs = ["10","0","1"], m = 1, n = 1
Strings with counts:
strs[0] = "10" → 1 zero, 1 one
strs[1] = "0" → 1 zero, 0 ones
strs[2] = "1" → 0 zeros, 1 one
k = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZE DP TABLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Base case: dp[0][j][l] = 0 for all j, l
Layer i=0: No strings
All values = 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
BUILD TABLE LAYER BY LAYER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Layer i=1: String "10" (1 zero, 1 one)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For j=0, l=0:
Can't include (need 1,1, have 0,0)
dp[1][0][0] = dp[0][0][0] = 0
For j=0, l=1:
Can't include (need 1 zero, have 0)
dp[1][0][1] = dp[0][0][1] = 0
For j=1, l=0:
Can't include (need 1 one, have 0)
dp[1][1][0] = dp[0][1][0] = 0
For j=1, l=1:
Don't include: dp[0][1][1] = 0
Include: 1 + dp[0][0][0] = 1 ✓
dp[1][1][1] = max(0, 1) = 1
Layer 1 result:
l: 0 1
j=0 0 0
j=1 0 1
Layer i=2: String "0" (1 zero, 0 ones)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For j=0, l=0:
Can't include (need 1 zero, have 0)
dp[2][0][0] = dp[1][0][0] = 0
For j=0, l=1:
Can't include (need 1 zero, have 0)
dp[2][0][1] = dp[1][0][1] = 0
For j=1, l=0:
Don't include: dp[1][1][0] = 0
Include: 1 + dp[1][0][0] = 1 + 0 = 1 ✓
dp[2][1][0] = max(0, 1) = 1
For j=1, l=1:
Don't include: dp[1][1][1] = 1
Include: 1 + dp[1][0][1] = 1 + 0 = 1
dp[2][1][1] = max(1, 1) = 1
Layer 2 result:
l: 0 1
j=0 0 0
j=1 1 1
Layer i=3: String "1" (0 zeros, 1 one)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For j=0, l=0:
Can't include (need 1 one, have 0)
dp[3][0][0] = dp[2][0][0] = 0
For j=0, l=1:
Don't include: dp[2][0][1] = 0
Include: 1 + dp[2][0][0] = 1 + 0 = 1 ✓
dp[3][0][1] = max(0, 1) = 1
For j=1, l=0:
Can't include (need 1 one, have 0)
dp[3][1][0] = dp[2][1][0] = 1
For j=1, l=1:
Don't include: dp[2][1][1] = 1
Include: 1 + dp[2][1][0] = 1 + 1 = 2 ✓
dp[3][1][1] = max(1, 2) = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP TABLE (Layer 3):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
l: 0 1
j=0 0 1
j=1 1 2
Answer: dp[3][1][1] = 2 ✓
This means:
Using first 3 strings with budget (1,1),
we can select maximum 2 strings.
Those strings are: "0" and "1"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why This Works - Visual Understanding:
Each cell dp[i][j][l] answers:
"Max strings using first i strings
with budget (j zeros, l ones)"
To compute dp[i][j][l], we look at:
1. Previous layer, same position: dp[i-1][j][l]
(don't use current string)
2. Previous layer, reduced budget: dp[i-1][j-zeros][l-ones]
(use current string)
If using the string gives more, take it!
Build table layer by layer, each using previous layer!
Classic 2D Knapsack pattern! 🎯
📊 Complexity Analysis
Time Complexity: O(k × m × n)
k = length of strs
m = max zeros
n = max ones
Outer loop: k iterations (each string)
Middle loop: m iterations (zeros)
Inner loop: n iterations (ones)
Total: k × m × n
For k=600, m=100, n=100:
600 × 100 × 100 = 6,000,000 operations
Very manageable! ✓
Space Complexity: O(k × m × n)
3D DP table of size (k+1) × (m+1) × (n+1)
Total: O(k × m × n)
🟣 Approach 4: Space-Optimized DP (2D Array)
💡 Intuition
The clever observation: We only need previous layer!
Notice in 3D DP:
dp[i][j][l] only depends on dp[i-1][j][l] and dp[i-1][j-zeros][l-ones]
We only look at PREVIOUS LAYER!
We don't need the entire 3D cube!
Optimization:
Instead of 3D array: dp[k][m][n]
Use 2D array: dp[m][n]
Process strings one by one, updating same 2D table
Process backwards (right to left, bottom to top) to avoid overwriting!
📝 Implementation
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// dp[j][l] = max strings with (j,l) budget
int[][] dp = new int[m + 1][n + 1];
// Base case: 0 budget = 0 strings (already initialized)
// Process each string
for (String str : strs) {
// Count 0's and 1's
int zeros = 0, ones = 0;
for (char c : str.toCharArray()) {
if (c == '0') zeros++;
else ones++;
}
// Traverse backwards to avoid overwriting!
for (int j = m; j >= zeros; j--) {
for (int l = n; l >= ones; l--) {
dp[j][l] = Math.max(
dp[j][l],
1 + dp[j - zeros][l - ones]
);
}
}
}
return dp[m][n];
}
}
🔍 Detailed Dry Run: strs = ["10","0","1"], m = 1, n = 1
Strings with counts:
"10" → 1 zero, 1 one
"0" → 1 zero, 0 ones
"1" → 0 zeros, 1 one
dp = [[0, 0],
[0, 0]]
j: 0 1
l:0 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PROCESS EACH STRING
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process "10" (1 zero, 1 one):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Traverse j from 1 to 1, l from 1 to 1:
j=1, l=1:
dp[1][1] = max(dp[1][1], 1 + dp[0][0])
= max(0, 1 + 0)
= 1 ✓
dp = [[0, 0],
[0, 1]]
Process "0" (1 zero, 0 ones):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Traverse j from 1 to 1, l from 1 to 0:
j=1, l=1:
dp[1][1] = max(dp[1][1], 1 + dp[0][1])
= max(1, 1 + 0)
= 1
j=1, l=0:
dp[1][0] = max(dp[1][0], 1 + dp[0][0])
= max(0, 1 + 0)
= 1 ✓
dp = [[0, 0],
[1, 1]]
Process "1" (0 zeros, 1 one):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Traverse j from 1 to 0, l from 1 to 1:
j=1, l=1:
dp[1][1] = max(dp[1][1], 1 + dp[1][0])
= max(1, 1 + 1)
= 2 ✓
j=0, l=1:
dp[0][1] = max(dp[0][1], 1 + dp[0][0])
= max(0, 1 + 0)
= 1 ✓
dp = [[0, 1],
[1, 2]]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP TABLE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
l: 0 1
j=0 0 1
j=1 1 2
Answer: dp[1][1] = 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 2 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why Backwards Processing Matters:
CRITICAL: Process j and l from high to low!
Why?
If we go low to high:
dp[j-zeros][l-ones] gets updated first
Then dp[j][l] uses the NEW value
This means using same string MULTIPLE times! ❌
If we go high to low:
dp[j][l] uses OLD dp[j-zeros][l-ones]
This means using each string at most ONCE! ✓
Same principle as 1D Knapsack optimization!
Backwards preserves 0/1 property! 🔑
📊 Complexity Analysis
Time Complexity: O(k × m × n)
Same as 3D approach
But with MUCH better space!
Space Complexity: O(m × n)
Only 2D array of size (m+1) × (n+1)
MUCH better than O(k × m × n)!
Optimal space! ✓
📊 Approach Comparison
┌──────────────────────────────────────────────────────────────┐
│ ONES AND ZEROES - APPROACH COMPARISON │
├──────────────┬───────────┬───────────┬────────────┬──────────┤
│ Approach │ Time │ Space │ Clarity │Interview │
├──────────────┼───────────┼───────────┼────────────┼──────────┤
│ Brute Force │ O(2^k) │ O(k) │ High │ Start │
│ Memoization │ O(k×m×n) │ O(k×m×n) │ Good │ Good │
│ 3D DP │ O(k×m×n) │ O(k×m×n) │ Best │ Best │
│ 2D DP │ O(k×m×n) │ O(m×n) │ Optimal ✓ │ Optimal ✓│
└──────────────┴───────────┴───────────┴────────────┴──────────┘
k = length of strs, m = max zeros, n = max ones
For interviews: Show 3D DP first, then optimize to 2D!
💻 Complete Working Code
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
return dp2D(strs, m, n);
}
// Approach 4: Space-Optimized 2D DP - O(k×m×n) time, O(m×n) space
private int dp2D(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (String str : strs) {
int zeros = 0, ones = 0;
for (char c : str.toCharArray()) {
if (c == '0')
zeros++;
else
ones++;
}
// Process backwards to avoid overwriting!
for (int j = m; j >= zeros; j--) {
for (int l = n; l >= ones; l--) {
dp[j][l] = Math.max(dp[j][l], 1 + dp[j - zeros][l - ones]);
}
}
}
return dp[m][n];
}
// Approach 3: 3D DP - O(k×m×n) time, O(k×m×n) space
private int dp3D(String[] strs, int m, int n) {
int k = strs.length;
int[][][] dp = new int[k + 1][m + 1][n + 1];
for (int i = 1; i <= k; i++) {
int zeros = 0, ones = 0;
for (char c : strs[i - 1].toCharArray()) {
if (c == '0')
zeros++;
else
ones++;
}
for (int j = 0; j <= m; j++) {
for (int l = 0; l <= n; l++) {
dp[i][j][l] = dp[i - 1][j][l];
if (j >= zeros && l >= ones) {
dp[i][j][l] = Math.max(dp[i][j][l], 1 + dp[i - 1][j - zeros][l - ones]);
}
}
}
}
return dp[k][m][n];
}
// Approach 2: Memoization - O(k×m×n) time, O(k×m×n) space
private int[][][] memo;
private int memoization(String[] strs, int m, int n) {
memo = new int[strs.length][m + 1][n + 1];
for (int i = 0; i < strs.length; i++) {
for (int j = 0; j <= m; j++) {
for (int l = 0; l <= n; l++) {
memo[i][j][l] = -1;
}
}
}
return helperMemo(strs, 0, m, n);
}
private int helperMemo(String[] strs, int index, int m, int n) {
if (index >= strs.length)
return 0;
if (memo[index][m][n] != -1)
return memo[index][m][n];
int zeros = 0, ones = 0;
for (char c : strs[index].toCharArray()) {
if (c == '0')
zeros++;
else
ones++;
}
int skip = helperMemo(strs, index + 1, m, n);
int include = 0;
if (m >= zeros && n >= ones) {
include = 1 + helperMemo(strs, index + 1, m - zeros, n - ones);
}
memo[index][m][n] = Math.max(skip, include);
return memo[index][m][n];
}
// Approach 1: Brute Force - O(2^k) time
private int bruteForce(String[] strs, int m, int n) {
return helperBrute(strs, 0, m, n);
}
private int helperBrute(String[] strs, int index, int m, int n) {
if (index >= strs.length)
return 0;
int zeros = 0, ones = 0;
for (char c : strs[index].toCharArray()) {
if (c == '0')
zeros++;
else
ones++;
}
int skip = helperBrute(strs, index + 1, m, n);
int include = 0;
if (m >= zeros && n >= ones) {
include = 1 + helperBrute(strs, index + 1, m - zeros, n - ones);
}
return Math.max(skip, include);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findMaxForm(new String[] { "10", "0001", "111001", "1", "0" }, 5, 3) == 4);
System.out.println(s.findMaxForm(new String[] { "10", "0", "1" }, 1, 1) == 2);
}
}
🔑 Key Insights
Multi-Dimensional Knapsack:
REGULAR 0/1 KNAPSACK:
One constraint: weight ≤ W
dp[weight] = max value
THIS PROBLEM (2D Knapsack):
Two constraints: zeros ≤ m AND ones ≤ n
dp[zeros][ones] = max count
Key difference: TWO dimensions of budget!
This is the canonical Multi-Dimensional Knapsack! 🔑
Budget Tracking:
Each string has TWO costs:
- Number of 0's
- Number of 1's
We have TWO budgets:
- m 0's total
- n 1's total
Must track BOTH simultaneously!
Pattern Recognition:
This extends 0/1 Knapsack to 2D!
Similar problems:
- Target Sum (two choices: + or -)
- Partition Equal Subset Sum (one target)
- This problem (two targets: zeros and ones)
All follow 0/1 Knapsack pattern! 🎯
Space Optimization:
3D DP: O(k × m × n) space
2D DP: O(m × n) space
How? Only need previous layer!
Key: Process backwards to avoid overwriting!
Same technique as 1D Knapsack optimization! ✓
🎪 Memory Aid
"Two budgets: zeros AND ones!"
"Each string costs (zeros, ones)!"
"Maximize count within both limits!"
"Process backwards to preserve 0/1!" ✨
⚠️ Common Mistakes
- ❌ Treating as single-constraint knapsack
- ❌ Not counting 0's and 1's correctly
- ❌ Forgetting to check BOTH m and n before including
- ❌ Processing forward in 2D DP (uses string multiple times!)
- ❌ Off-by-one errors with string indices
✅ Interview Talking Points
"This is a Multi-Dimensional 0/1 Knapsack problem.
Key insight:
Regular Knapsack has ONE constraint (weight).
This problem has TWO constraints (zeros AND ones).
Each string costs (zeros, ones).
We have budget (m, n).
Maximize number of strings selected.
DP Approach:
dp[i][j][l] = max strings using first i strings
with budget (j zeros, l ones)
Base case: dp[0][j][l] = 0 (no strings)
For each string, two choices:
Skip: dp[i-1][j][l]
Include: 1 + dp[i-1][j-zeros][l-ones]
Take maximum!
Space optimization:
Only need previous layer → use 2D array
Process backwards (high to low) to avoid using string twice
Complexity: O(k×m×n) time, O(m×n) space
where k = number of strings
This is optimal for this problem!"
📝 Quick Revision Notes
⚡ Quick Implementation
public class Solution {
public int findMaxForm(String[] ss, int m, int n) {
// return recursive(ss, 0, m, n);
// // How many params get changes in every method call, that
// // number of dimensions of matrix needs to be taken.
// Integer[][][] memo = new Integer[ss.length][m + 1][n + 1];
// return topDown(ss, 0, m, n, memo);
return bottomUp(ss, m, n);
}
private int bottomUp(String[] ss, int m, int n) {
int len = ss.length;
int[][][] dp = new int[len + 1][m + 1][n + 1];
for (int i = 1; i <= len; i++) {
int zeros = 0;
int ones = 0;
for (char c : ss[i - 1].toCharArray()) {
if (c == '0') {
zeros++;
} else if (c == '1') {
ones++;
}
}
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
dp[i][j][k] = dp[i - 1][j][k];
if (j - zeros >= 0 && k - ones >= 0) {
dp[i][j][k] = Math.max(1 + dp[i - 1][j - zeros][k - ones], dp[i][j][k]);
}
}
}
}
return dp[len][m][n];
}
private int topDown(String[] ss, int index, int m, int n, Integer[][][] memo) {
if (index == ss.length || m < 0 || n < 0) {
return 0;
}
if (memo[index][m][n] != null) {
return memo[index][m][n];
}
int zeros = 0;
int ones = 0;
for (char c : ss[index].toCharArray()) {
if (c == '0') {
zeros++;
} else if (c == '1') {
ones++;
}
}
int take = 0;
if (m - zeros >= 0 && n - ones >= 0) {
take = 1 + topDown(ss, index + 1, m - zeros, n - ones, memo);
}
int no_take = topDown(ss, index + 1, m, n, memo);
return memo[index][m][n] = Math.max(take, no_take);
}
private int recursive(String[] ss, int index, int m, int n) {
// step 4: base case
if (index == ss.length || m < 0 || n < 0) {
return 0;
}
// step 1: find number of zeros and ones in current string at index.
int zeros = 0;
int ones = 0;
for (char c : ss[index].toCharArray()) {
if (c == '0') {
zeros++;
} else if (c == '1') {
ones++;
}
}
// step 2: consider current string at index only if m >= zeros and n >= ones
int take = 0;
if (m - zeros >= 0 && n - ones >= 0) {
take = 1 + recursive(ss, index + 1, m - zeros, n - ones);
}
// step 3: skip current string at index
int no_take = recursive(ss, index + 1, m, n);
return Math.max(take, no_take);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findMaxForm(new String[] { "10", "0001", "111001", "1", "0" }, 5, 3) == 4);
System.out.println(s.findMaxForm(new String[] { "10", "0001", "111001", "1", "0" }, 4, 3) == 3);
System.out.println(s.findMaxForm(new String[] { "10", "0", "1" }, 1, 1) == 2);
}
}
🎉 Congratulations!
You've mastered Ones and Zeroes - Multi-Dimensional 0/1 Knapsack!
What You Learned:
✅ Multi-dimensional constraints - Two budgets: zeros and ones
✅ Budget tracking - Each item has two costs
✅ 0/1 Knapsack extension - 2D version
✅ Brute force - Try all subsets
✅ Memoization - Cache (index, m, n) states
✅ 3D DP - Bottom-up table building
✅ 2D DP - Space optimization (backwards processing!)
This is a beautiful extension of classic Knapsack to multiple dimensions! 🚀✨