Problem Description

The "Ones and Zeroes" problem from Leetcode asks you to find the largest subset of binary strings from a given array strs such that the subset contains at most m zeros and n ones in total. Each string in strs is made up only of the characters '0' and '1'. You cannot reuse any string more than once, and each string can be chosen at most once. The goal is to maximize the number of strings in the chosen subset while keeping within the limits for zeros and ones.

• Input: strs (array of binary strings), m (maximum number of zeros), n (maximum number of ones)
• Output: The size of the largest possible subset meeting the constraints
• Constraints: Each string can be used at most once and the sum of zeros and ones across the subset must not exceed m and n respectively.

Thought Process

At first glance, this problem looks similar to the classic Knapsack Problem, where you have a set of items (here, strings), each with a "cost" (number of zeros and ones), and you want to maximize the number of items (subset size) without exceeding your "budget" (m zeros and n ones). A brute-force approach would consider all possible subsets, count their zeros and ones, and keep track of the largest valid subset. However, this is computationally expensive (exponential time), especially as the number of strings grows.

To optimize, we can use dynamic programming to systematically build up solutions to subproblems, similar to how we solve the 0/1 knapsack. The key insight is to track, for each possible combination of zeros and ones, the maximum subset size achievable.

Solution Approach

We solve this problem using dynamic programming with a 2D array to represent the state:

• Step 1: For each string in strs, count the number of zeros and ones it contains.
• Step 2: Initialize a 2D DP array dp of size (m+1) x (n+1). Here, dp[i][j] represents the largest subset size that can be formed with at most i zeros and j ones.
• Step 3: For each string, update the DP table in reverse (from high to low for both zeros and ones) to avoid reusing the same string multiple times. For each cell dp[i][j], check if including the current string (if possible) would increase the subset size.
• Step 4: After processing all strings, dp[m][n] contains the size of the largest valid subset.

This approach ensures that each string is considered only once for each subproblem, and we never exceed the allowed number of zeros or ones.

Example Walkthrough

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

1. Count zeros and ones 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
2. Initialize dp[6][4] (since we use 0-based indexing, size is m+1 by n+1).
3. For each string, update the DP table in reverse:
   • After processing all strings, dp[5][3] will be 4, meaning the largest subset has 4 strings.
4. One possible subset: ["10", "0001", "1", "0"] (uses 5 zeros and 3 ones).

The DP table evolves by considering, for each cell, whether including a string gives a better result than excluding it.

Time and Space Complexity

• Brute-force approach: O(2^k * k), where k is the number of strings. Each subset is checked for validity, which is exponential and impractical for large k.
• Optimized DP approach: O(k * m * n), since for each of the k strings, we update up to m * n DP cells.
• Space complexity: O(m * n) for the DP table.

The DP approach is much more efficient and feasible for the given constraints.

Summary

The "Ones and Zeroes" problem is a two-dimensional variant of the classic knapsack problem. By recognizing this, we can use dynamic programming to efficiently compute the largest subset of binary strings that fit within the given zero and one constraints. The key insights are to count zeros and ones for each string, use a 2D DP table, and update it in reverse to avoid reusing strings. This approach is both elegant and efficient, transforming an exponential brute-force problem into a manageable polynomial-time solution.

Code Implementation

class Solution:
    def findMaxForm(self, strs, m, n):
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for s in strs:
            zeros = s.count('0')
            ones = s.count('1')
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
        return dp[m][n]
      

class Solution {
public:
    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 = count(s.begin(), s.end(), '0');
            int ones = count(s.begin(), s.end(), '1');
            for (int i = m; i >= zeros; --i) {
                for (int j = n; j >= ones; --j) {
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 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 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], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
      

var findMaxForm = function(strs, m, n) {
    const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
    for (let s of strs) {
        let zeros = 0, ones = 0;
        for (let c of s) {
            if (c === '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], dp[i - zeros][j - ones] + 1);
            }
        }
    }
    return dp[m][n];
};