Ones and Zeroes
Problem
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 0s and n 1s in the subset.
strs = ["10","0001","111001","1","0"], m = 5, n = 34def find_max_form(strs, m, n):
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
z = s.count('0'); o = s.count('1')
for i in range(m, z - 1, -1):
for j in range(n, o - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1)
return dp[m][n]function findMaxForm(strs, m, n) {
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (const s of strs) {
let z = 0, o = 0;
for (const c of s) c === '0' ? z++ : o++;
for (let i = m; i >= z; i--) {
for (let j = n; j >= o; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - z][j - o] + 1);
}
}
}
return dp[m][n];
}class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for (String s : strs) {
int z = 0, o = 0;
for (char c : s.toCharArray()) { if (c == '0') z++; else o++; }
for (int i = m; i >= z; i--) {
for (int j = n; j >= o; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - z][j - o] + 1);
}
}
}
return dp[m][n];
}
}int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (auto& s : strs) {
int z = count(s.begin(), s.end(), '0');
int o = (int)s.size() - z;
for (int i = m; i >= z; i--)
for (int j = n; j >= o; j--)
dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1);
}
return dp[m][n];
}Explanation
This is a 0/1 knapsack with two capacities instead of one. Each binary string is an item that "costs" some zeros and some ones, and our budget is m zeros and n ones. We want the largest number of strings we can pick. The state dp[i][j] = the most strings we can take using at most i zeros and j ones.
We process strings one at a time. For each string we count its zeros z and ones o, then decide for every budget whether taking it beats skipping it: dp[i][j] = max(dp[i][j], dp[i-z][j-o] + 1).
The crucial detail is iterating i and j in reverse (from m down to z, from n down to o). This guarantees that dp[i-z][j-o] still reflects the table before this string was added, so each string is used at most once.
Example: strs = ["10","0001","111001","1","0"], m = 5, n = 3. We can take {"10","0001","1","0"} — 4 strings using 4 zeros and 3 ones — so the answer is 4.
The final answer sits at dp[m][n]. Processing every string against the full budget grid gives the O(L · m · n) running time.