Ones and Zeroes (2D Knapsack)

🎯

Ones and Zeroes (2D Knapsack)

mediumDPAmazonGoogleFacebook

Imagine you have a collection of binary strings and a limited number of 0s and 1s you can use. How do you pick the maximum number of strings without exceeding your 0s and 1s budget?

💡 This problem is a classic example of a 2D knapsack variant where instead of one weight constraint, we have two constraints (count of zeros and ones). Beginners often struggle because it extends the classic knapsack problem to two dimensions, making brute force solutions explode exponentially and requiring careful dynamic programming to optimize.

📋

Problem Statement

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. Each 0 and 1 can only be used once across the chosen subset.

1 ≤ strs.length ≤ 6001 ≤ strs[i].length ≤ 1001 ≤ m, n ≤ 100

💡

Example

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

Output4

We can form the subset {"10", "0001", "1", "0"} which uses 5 zeros and 3 ones in total.

• Empty strs array → output 0
• m = 0 and n = 0 → output 0 since no zeros or ones can be used
• All strings contain only zeros → output limited by m
• All strings contain only ones → output limited by n

🔁

Why DP?

Why greedy fails:

A greedy approach that picks strings with the least zeros or ones first can fail. For example, picking many small strings with few zeros but many ones might prevent choosing a larger string that fits better overall, leading to suboptimal subsets.

DP state:

dp[i][j] represents the maximum number of strings that can be formed using at most i zeros and j ones from the strings considered so far.

Recurrence:dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) if i >= zeros and j >= ones

For each string, either skip it or include it if enough zeros and ones remain, updating dp accordingly.

⚠️

Common Mistakes

Iterating dp array forwards instead of backwards

Strings get counted multiple times, leading to incorrect results

✅ Iterate zeros and ones backwards when updating dp

Not counting zeros and ones correctly

Incorrect feasibility checks cause wrong dp updates

✅ Carefully count zeros and ones for each string before dp update

Not handling base cases in recursion

Stack overflow or incorrect results

✅ Return 0 when index reaches end of strings

Using mutable default arguments in recursion (Python)

Unexpected shared state across calls

✅ Avoid mutable defaults or use memo dict explicitly

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's exponential nature and the need for optimization. It lays the foundation for memoization and DP.

Intuition

Try every subset of strings, recursively deciding to include or exclude each string, and track zeros and ones used.

Algorithm

1. Define a recursive function that takes the current index and remaining zeros and ones.
2. If index is beyond last string, return 0.
3. For current string, count zeros and ones.
4. If enough zeros and ones remain, recurse including the string and excluding it, take max.
5. Return the maximum count found.

💡 The recursion tree grows exponentially because each string branches into two choices, making it hard to track without memoization.

Recurrence:f(i, m, n) = max(f(i+1, m, n), 1 + f(i+1, m - zeros_i, n - ones_i)) if m >= zeros_i and n >= ones_i else f(i+1, m, n)

</>

Code

from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    def count_zeros_ones(s: str) -> (int, int):
        zeros = s.count('0')
        ones = len(s) - zeros
        return zeros, ones

    def dfs(i: int, zeros_left: int, ones_left: int) -> int:
        if i == len(strs):
            return 0
        zeros, ones = count_zeros_ones(strs[i])
        res = dfs(i + 1, zeros_left, ones_left)  # skip current
        if zeros <= zeros_left and ones <= ones_left:
            res = max(res, 1 + dfs(i + 1, zeros_left - zeros, ones_left - ones))
        return res

    return dfs(0, m, n)

# Example usage:
if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4

Line Notes

def count_zeros_ones(s: str) -> (int, int):Helper to count zeros and ones in a string for reuse

if i == len(strs):Base case: no more strings to consider

res = dfs(i + 1, zeros_left, ones_left)Option 1: skip current string

if zeros <= zeros_left and ones <= ones_left:Check feasibility before including current string

import java.util.*;

public class OnesAndZeroes {
    public static int findMaxForm(String[] strs, int m, int n) {
        return dfs(strs, 0, m, n);
    }

    private static int dfs(String[] strs, int i, int zerosLeft, int onesLeft) {
        if (i == strs.length) return 0;
        int zeros = 0, ones = 0;
        for (char c : strs[i].toCharArray()) {
            if (c == '0') zeros++;
            else ones++;
        }
        int res = dfs(strs, i + 1, zerosLeft, onesLeft); // skip
        if (zeros <= zerosLeft && ones <= onesLeft) {
            res = Math.max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones));
        }
        return res;
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        System.out.println(findMaxForm(strs, m, n)); // 4
    }
}

Line Notes

if (i == strs.length) return 0;Base case: no more strings to process

for (char c : strs[i].toCharArray())Count zeros and ones in current string

int res = dfs(strs, i + 1, zerosLeft, onesLeft);Skip current string option

if (zeros <= zerosLeft && ones <= onesLeft)Include current string if feasible

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int dfs(const vector<string>& strs, int i, int zerosLeft, int onesLeft) {
    if (i == strs.size()) return 0;
    int zeros = 0, ones = 0;
    for (char c : strs[i]) {
        if (c == '0') zeros++;
        else ones++;
    }
    int res = dfs(strs, i + 1, zerosLeft, onesLeft); // skip
    if (zeros <= zerosLeft && ones <= onesLeft) {
        res = max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones));
    }
    return res;
}

int findMaxForm(vector<string>& strs, int m, int n) {
    return dfs(strs, 0, m, n);
}

int main() {
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5, n = 3;
    cout << findMaxForm(strs, m, n) << endl; // 4
    return 0;
}

Line Notes

if (i == strs.size()) return 0;Base case: no more strings to consider

for (char c : strs[i])Count zeros and ones in current string

int res = dfs(strs, i + 1, zerosLeft, onesLeft);Option to skip current string

if (zeros <= zerosLeft && ones <= onesLeft)Include current string if possible

function findMaxForm(strs, m, n) {
    function countZerosOnes(s) {
        let zeros = 0, ones = 0;
        for (let ch of s) {
            if (ch === '0') zeros++;
            else ones++;
        }
        return [zeros, ones];
    }

    function dfs(i, zerosLeft, onesLeft) {
        if (i === strs.length) return 0;
        const [zeros, ones] = countZerosOnes(strs[i]);
        let res = dfs(i + 1, zerosLeft, onesLeft); // skip
        if (zeros <= zerosLeft && ones <= onesLeft) {
            res = Math.max(res, 1 + dfs(i + 1, zerosLeft - zeros, onesLeft - ones));
        }
        return res;
    }

    return dfs(0, m, n);
}

// Example usage:
const strs = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
console.log(findMaxForm(strs, m, n)); // 4

Line Notes

function countZerosOnes(s) {Helper to count zeros and ones in a string

if (i === strs.length) return 0;Base case: no more strings to process

let res = dfs(i + 1, zerosLeft, onesLeft);Skip current string option

if (zeros <= zerosLeft && ones <= onesLeft)Include current string if feasible

⏱

Complexity

TimeO(2^n)

SpaceO(n)

Each string can be included or excluded, leading to 2^n subsets. The recursion stack depth is O(n).

💡 For n=20, this means over a million calls, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's nature and motivate DP.

🧠

Top-Down Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving performance while keeping the recursive structure.

Intuition

Use a dictionary or map keyed by (index, zeros_left, ones_left) to store results of subproblems and reuse them.

Algorithm

1. Define a recursive function with parameters index, zeros_left, ones_left.
2. Before computing, check if result is in memo; if yes, return it.
3. Compute by skipping or including current string if feasible.
4. Store the result in memo and return it.

💡 Memoization reduces exponential calls to polynomial by caching repeated states.

Recurrence:f(i, m, n) = max(f(i+1, m, n), 1 + f(i+1, m - zeros_i, n - ones_i)) if m >= zeros_i and n >= ones_i else f(i+1, m, n)

</>

Code

from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    memo = {}

    def count_zeros_ones(s: str) -> (int, int):
        zeros = s.count('0')
        ones = len(s) - zeros
        return zeros, ones

    def dfs(i: int, zeros_left: int, ones_left: int) -> int:
        if i == len(strs):
            return 0
        if (i, zeros_left, ones_left) in memo:
            return memo[(i, zeros_left, ones_left)]
        zeros, ones = count_zeros_ones(strs[i])
        res = dfs(i + 1, zeros_left, ones_left)  # skip
        if zeros <= zeros_left and ones <= ones_left:
            res = max(res, 1 + dfs(i + 1, zeros_left - zeros, ones_left - ones))
        memo[(i, zeros_left, ones_left)] = res
        return res

    return dfs(0, m, n)

# Example usage:
if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4

Line Notes

memo = {}Cache to store results of subproblems

if (i, zeros_left, ones_left) in memo:Return cached result to avoid recomputation

memo[(i, zeros_left, ones_left)] = resStore computed result for future calls

res = max(res, 1 + dfs(i + 1, zeros_left - zeros, ones_left - ones))Include current string if feasible and update max

import java.util.*;

public class OnesAndZeroesMemo {
    private static Map<String, Integer> memo = new HashMap<>();

    public static int findMaxForm(String[] strs, int m, int n) {
        return dfs(strs, 0, m, n);
    }

    private static int dfs(String[] strs, int i, int zerosLeft, int onesLeft) {
        if (i == strs.length) return 0;
        String key = i + "," + zerosLeft + "," + onesLeft;
        if (memo.containsKey(key)) return memo.get(key);
        int zeros = 0, ones = 0;
        for (char c : strs[i].toCharArray()) {
            if (c == '0') zeros++;
            else ones++;
        }
        int res = dfs(strs, i + 1, zerosLeft, onesLeft); // skip
        if (zeros <= zerosLeft && ones <= onesLeft) {
            res = Math.max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones));
        }
        memo.put(key, res);
        return res;
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        System.out.println(findMaxForm(strs, m, n)); // 4
    }
}

Line Notes

private static Map<String, Integer> memo = new HashMap<>();Memoization cache keyed by state string

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

memo.put(key, res);Store computed result for reuse

res = Math.max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones));Include current string if possible

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

string makeKey(int i, int zerosLeft, int onesLeft) {
    return to_string(i) + "," + to_string(zerosLeft) + "," + to_string(onesLeft);
}

int dfs(const vector<string>& strs, int i, int zerosLeft, int onesLeft, unordered_map<string,int>& memo) {
    if (i == strs.size()) return 0;
    string key = makeKey(i, zerosLeft, onesLeft);
    if (memo.count(key)) return memo[key];
    int zeros = 0, ones = 0;
    for (char c : strs[i]) {
        if (c == '0') zeros++;
        else ones++;
    }
    int res = dfs(strs, i + 1, zerosLeft, onesLeft, memo); // skip
    if (zeros <= zerosLeft && ones <= onesLeft) {
        res = max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones, memo));
    }
    memo[key] = res;
    return res;
}

int findMaxForm(vector<string>& strs, int m, int n) {
    unordered_map<string,int> memo;
    return dfs(strs, 0, m, n, memo);
}

int main() {
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5, n = 3;
    cout << findMaxForm(strs, m, n) << endl; // 4
    return 0;
}

Line Notes

unordered_map<string,int>& memoMemoization cache passed by reference

if (memo.count(key)) return memo[key];Return cached result if present

memo[key] = res;Store computed result for reuse

res = max(res, 1 + dfs(strs, i + 1, zerosLeft - zeros, onesLeft - ones, memo));Include current string if feasible

function findMaxForm(strs, m, n) {
    const memo = new Map();

    function countZerosOnes(s) {
        let zeros = 0, ones = 0;
        for (let ch of s) {
            if (ch === '0') zeros++;
            else ones++;
        }
        return [zeros, ones];
    }

    function dfs(i, zerosLeft, onesLeft) {
        if (i === strs.length) return 0;
        const key = i + ',' + zerosLeft + ',' + onesLeft;
        if (memo.has(key)) return memo.get(key);
        const [zeros, ones] = countZerosOnes(strs[i]);
        let res = dfs(i + 1, zerosLeft, onesLeft); // skip
        if (zeros <= zerosLeft && ones <= onesLeft) {
            res = Math.max(res, 1 + dfs(i + 1, zerosLeft - zeros, onesLeft - ones));
        }
        memo.set(key, res);
        return res;
    }

    return dfs(0, m, n);
}

// Example usage:
const strs = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
console.log(findMaxForm(strs, m, n)); // 4

Line Notes

const memo = new Map();Memoization cache to store computed states

if (memo.has(key)) return memo.get(key);Return cached result if available

memo.set(key, res);Store computed result for reuse

res = Math.max(res, 1 + dfs(i + 1, zerosLeft - zeros, onesLeft - ones));Include current string if feasible

⏱

Complexity

TimeO(n * m * n)

SpaceO(n * m * n)

Memoization reduces calls to unique states bounded by number of strings and zero/one budgets.

💡 For n=600, m=100, n=100, this is feasible but still expensive.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for interview constraints and is a natural step from brute force.

🧠

Bottom-Up Tabulation (2D DP Table)

💡 Tabulation builds the solution iteratively from smaller subproblems, often easier to understand and debug than recursion with memoization.

Intuition

Use a 2D dp array where dp[i][j] stores max strings with i zeros and j ones. For each string, update dp by considering inclusion.

Algorithm

1. Initialize a 2D dp array of size (m+1) x (n+1) with zeros.
2. For each string, count zeros and ones.
3. Iterate zeros from m down to zeros count, and ones from n down to ones count.
4. Update dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) to include current string.
5. Return dp[m][n] as the answer.

💡 Backward iteration ensures each string is counted once per iteration, preserving 0/1 knapsack logic.

Recurrence:dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) if i >= zeros and j >= ones

</>

Code

from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zeros = s.count('0')
        ones = len(s) - zeros
        for i in range(m, zeros - 1, -1):
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

    return dp[m][n]

# Example usage:
if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4

Line Notes

dp = [[0] * (n + 1) for _ in range(m + 1)]Initialize DP table with zeros for all zero/one budgets

for s in strs:Process each string to update dp

for i in range(m, zeros - 1, -1):Iterate zeros backwards to avoid reuse in same iteration

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])Update dp with max of skipping or including current string

public class OnesAndZeroesTab {
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        System.out.println(findMaxForm(strs, m, n)); // 4
    }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];Create DP table for zero and one budgets

for (String s : strs)Process each string

for (int i = m; i >= zeros; i--)Iterate zeros backwards to avoid double counting

dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (const string& s : strs) {
        int zeros = 0, ones = 0;
        for (char c : s) {
            if (c == '0') zeros++;
            else ones++;
        }
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);
            }
        }
    }
    return dp[m][n];
}

int main() {
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5, n = 3;
    cout << findMaxForm(strs, m, n) << endl; // 4
    return 0;
}

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));Initialize DP table with zeros

for (const string& s : strs)Iterate over each string

for (int i = m; i >= zeros; i--)Backward iteration to prevent reuse in same iteration

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string

function findMaxForm(strs, m, n) {
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (const s of strs) {
        let zeros = 0, ones = 0;
        for (const ch of s) {
            if (ch === '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], 1 + dp[i - zeros][j - ones]);
            }
        }
    }

    return dp[m][n];
}

// Example usage:
const strs = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
console.log(findMaxForm(strs, m, n)); // 4

Line Notes

const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));Initialize 2D DP array with zeros

for (const s of strs)Process each string

for (let i = m; i >= zeros; i--)Backward iteration to avoid double counting

dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string

⏱

Complexity

TimeO(l * m * n)

SpaceO(m * n)

For each string (l), we update a dp table of size m*n.

💡 For m=100, n=100, and l=600, this is efficient and practical.

Interview Verdict: Accepted

This is the preferred approach in interviews due to clarity and efficiency.

🧠

Space Optimized Bottom-Up (1D DP Array)

💡 We can optimize space by using a single 2D array and updating it in reverse order, reducing memory usage while preserving correctness.

Intuition

Since dp[i][j] depends only on dp[i - zeros][j - ones], we can update dp in place backwards to reuse the same array.

Algorithm

1. Initialize a 2D dp array of size (m+1) x (n+1) with zeros.
2. For each string, count zeros and ones.
3. Iterate zeros from m down to zeros count, and ones from n down to ones count.
4. Update dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]) in place.
5. Return dp[m][n] as the answer.

💡 Backward iteration prevents overwriting states needed for future calculations in the same iteration.

Recurrence:dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

</>

Code

from typing import List

def findMaxForm(strs: List[str], m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zeros = s.count('0')
        ones = len(s) - zeros
        for i in range(m, zeros - 1, -1):
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])

    return dp[m][n]

# Example usage:
if __name__ == '__main__':
    strs = ["10", "0001", "111001", "1", "0"]
    m, n = 5, 3
    print(findMaxForm(strs, m, n))  # Output: 4

Line Notes

dp = [[0] * (n + 1) for _ in range(m + 1)]Initialize DP table

for s in strs:Process each string

for i in range(m, zeros - 1, -1):Backward iteration to avoid double counting

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones])Update dp with max of skipping or including string

public class OnesAndZeroesSpaceOpt {
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;
        System.out.println(findMaxForm(strs, m, n)); // 4
    }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];Initialize DP table

for (int i = m; i >= zeros; i--)Backward iteration to prevent reuse of updated states

dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string

for (String s : strs)Process each string

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int findMaxForm(vector<string>& strs, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (const string& s : strs) {
        int zeros = 0, ones = 0;
        for (char c : s) {
            if (c == '0') zeros++;
            else ones++;
        }
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);
            }
        }
    }
    return dp[m][n];
}

int main() {
    vector<string> strs = {"10", "0001", "111001", "1", "0"};
    int m = 5, n = 3;
    cout << findMaxForm(strs, m, n) << endl; // 4
    return 0;
}

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));Initialize DP table

for (int i = m; i >= zeros; i--)Backward iteration to avoid double counting

dp[i][j] = max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string

for (const string& s : strs)Process each string

function findMaxForm(strs, m, n) {
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (const s of strs) {
        let zeros = 0, ones = 0;
        for (const ch of s) {
            if (ch === '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], 1 + dp[i - zeros][j - ones]);
            }
        }
    }

    return dp[m][n];
}

// Example usage:
const strs = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
console.log(findMaxForm(strs, m, n)); // 4

Line Notes

const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));Initialize DP table

for (let i = m; i >= zeros; i--)Backward iteration to avoid double counting

dp[i][j] = Math.max(dp[i][j], 1 + dp[i - zeros][j - ones]);Update dp with max of skipping or including string

for (const s of strs)Process each string

⏱

Complexity

TimeO(l * m * n)

SpaceO(m * n)

Same as tabulation but with optimized space usage.

💡 This approach uses less memory but same time complexity as tabulation.

Interview Verdict: Accepted

Space optimization is a nice-to-have in interviews to demonstrate deeper understanding.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the bottom-up tabulation (Approach 3) is usually best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n)	Yes (deep recursion)	No	Mention only - never code
2. Top-Down Memoization	O(n * m * n)	O(n * m * n)	Possible (deep recursion)	Yes (with extra tracking)	Good for explaining optimization
3. Bottom-Up Tabulation	O(l * m * n)	O(m * n)	No	Yes (with parent pointers)	Best to code in interview
4. Space Optimized Bottom-Up	O(l * m * n)	O(m * n)	No	Harder	Mention if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when and how to present them in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem's complexity.Introduce memoization to optimize overlapping subproblems.Present the bottom-up DP solution as the optimal approach.Optionally mention space optimization if time permits.

Time Allocation

Clarify: 2min → Brute Force: 3min → Memoization: 4min → Tabulation: 5min → Testing: 3min. Total ~17min

What the Interviewer Tests

Understanding of knapsack variants, ability to optimize brute force, knowledge of DP states and transitions, and coding accuracy.

Common Follow-ups

• What if we want to return the actual subset? → Use parent pointers or reconstruct from dp table.
• Can this be solved with a greedy approach? → No, greedy fails due to two constraints.

💡 These follow-ups test deeper understanding and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves selecting subsets with constraints; 2) Constraints involve two resources (zeros and ones); 3) Maximize count or value; 4) Classic knapsack structure with two dimensions.

Signature Phrases

"at most m zeros and n ones""maximum number of strings"

NOT This Pattern When

Problems with unlimited item usage or without resource constraints are different patterns.

Similar Problems

0/1 Knapsack - classic single constraint knapsackCoin Change - counting ways with constraintsTarget Sum - subset sum variant with sign constraints

Practice

1. Consider the following Python code for counting the number of ways to make change. What is the output when calling change(5, [1, 2, 5])?

easy

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0] since dp[0]=1.

2. Step 2: Update dp for each coin

   For coin=1: dp becomes [1,1,1,1,1,1]; for coin=2: dp updates to [1,1,2,2,3,3]; for coin=5: dp updates to [1,1,2,2,3,4].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   dp[5] = 4 matches known output [OK]

Hint: Trace dp updates coin by coin [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Confusing permutations with combinations

2. What is the time complexity of the optimal bottom-up dynamic programming solution for the Coin Change II problem with n coins and target amount amount?

medium

A. O(amount^2)

B. O(n + amount)

C. O(2^amount)

D. O(n * amount)

Solution

1. Step 1: Identify loops in code

   Outer loop iterates over n coins, inner loop iterates over amount from coin to amount.

2. Step 2: Calculate complexity

   Each dp[w] update is O(1), total updates are roughly n * amount, so time complexity is O(n * amount).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over coins and amounts confirm O(n * amount) [OK]

Hint: Count nested loops and their ranges [OK]

Common Mistakes:

• Confusing amount with n
• Forgetting recursion stack space
• Assuming quadratic in amount

3. What is the time complexity of the DP with bitmask tabulation approach for partitioning an array of size n into k equal sum subsets, where the algorithm iterates over all subsets and elements?

medium

A. O(k^n) because it tries all assignments of elements to k buckets

B. O(n * 2^n) because it iterates over all subsets and elements

C. O(n * target) where target is the subset sum

D. O(2^n * n^2) due to nested loops over subsets and elements

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop iterates over all subsets (2^n), inner loop over n elements.

2. Step 2: Calculate total complexity

   Combining loops gives O(n * 2^n). The target sum does not affect iteration count directly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP bitmask iterates all subsets and elements [OK]

Hint: Bitmask DP complexity is n times 2^n subsets [OK]

Common Mistakes:

• Confusing brute force backtracking complexity with DP complexity
• Assuming complexity depends on target sum

4. Suppose the coin change problem is modified so that each coin can only be used at most once (0/1 knapsack variant). Which of the following changes to the bottom-up DP approach correctly solves this variant?

hard

A. Use a 2D dp array where dp[i][j] represents minimum coins to make amount j using first i coins, iterating coins outer and amounts inner

B. Sort coins and greedily pick largest coins without repetition until amount is reached

C. Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage)

D. Use the same 1D dp but iterate amounts outer and coins inner, updating dp[j] only if dp[j - coin] was from previous iteration

Solution

1. Step 1: Understand the 0/1 usage constraint

   Each coin can be used once, so we must track usage per coin, requiring 2D dp.

2. Step 2: Identify correct DP structure

   2D dp with dp[i][j] = min coins to make j using first i coins ensures no reuse; iterate coins outer, amounts inner.

3. Step 3: Why other options fail

   Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage) allows unlimited reuse; B is greedy and incorrect; D misuses 1D dp which is for unbounded usage.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   0/1 knapsack requires 2D dp to track coin usage [OK]

Hint: 0/1 knapsack needs 2D dp to prevent reuse [OK]

Common Mistakes:

• Using unbounded knapsack DP for 0/1 problem
• Assuming greedy works for minimum coins

5. Suppose now you want to count the number of ways to make change but coins can be used at most once each (no reuse). Which modification to the DP approach correctly solves this variant?

hard

A. Use 1D DP iterating amounts forwards but reset dp array after each coin

B. Use 2D DP with dp[i][w] representing ways using first i coins for amount w, iterating amounts forwards

C. Use the same 1D DP but iterate amounts backwards from amount down to coin value

D. Use greedy approach picking largest coins first until amount is reached

Solution

1. Step 1: Understand no reuse constraint

   Each coin can be used once, so combinations must not count repeated usage of the same coin.

2. Step 2: Modify DP iteration order

   Iterating amounts backwards in 1D DP ensures each coin contributes only once per amount, preventing reuse.

3. Step 3: Confirm correctness

   This approach correctly counts combinations without reuse, unlike forward iteration which allows multiple usage.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Backward iteration in 1D DP enforces single usage per coin [OK]

Hint: Backward iteration prevents coin reuse in 1D DP [OK]

Common Mistakes:

• Using forward iteration allows unlimited reuse
• Resetting dp array loses accumulated counts
• Greedy approach misses many combinations