Ones and Zeroes

How it works

Notice that when computing dp[i], we only need values from dp[i-1]. This means we can reduce the 3D table to a 2D table.

The key trick is to iterate the budgets in reverse order. When we update dp[j][k], we need the old values of dp[j-zeros][k-ones]. By iterating backward, we ensure these values have not been overwritten yet in the current iteration.

Steps

1. Preprocess each string to count its zeros and ones.
2. Create a 2D DP table of size (m + 1) x (n + 1), initialized to 0.
3. For each string with zeros zeros and ones ones:
   • For j from m down to zeros:
     • For k from n down to ones:
       • Update: dp[j][k] = max(dp[j][k], 1 + dp[j-zeros][k-ones]).
4. Return dp[m][n].

Complexity

• Time complexity: O(m * n * N)
• Space complexity: O(m * n + N)

Where N represents the number of binary strings, and m and n are the maximum allowable counts of zeros and ones, respectively.

Things to watch for

Iterating Forward Instead of Backward in Space-Optimized DP

When using the 2D space-optimized solution, iterating from small values to large values causes the same string to be counted multiple times in one iteration. You must iterate j from m down to zeros and k from n down to ones to ensure each string is used at most once per subset.

Confusing Zeros and Ones Counts

Mixing up which index stores the count of zeros versus ones leads to incorrect budget checks. Consistently use index 0 for zeros and index 1 for ones (or vice versa) throughout the solution, and ensure the comparison matches this convention.

Treating This as Unbounded Knapsack

This is a 0/1 knapsack problem where each string can be selected at most once. Solutions that allow selecting the same string multiple times will overcount and return incorrect results. Each string must be processed exactly once, either included or excluded.

from typing import List

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        arr = [[0, 0] for _ in range(len(strs))]
        for i, s in enumerate(strs):
            for c in s:
                arr[i][ord(c) - ord('0')] += 1

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

        for zeros, ones in arr:
            for j in range(m, zeros - 1, -1):
                for k in range(n, ones - 1, -1):
                    dp[j][k] = max(dp[j][k], 1 + dp[j - zeros][k - ones])

        return dp[m][n]

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> arr(strs.size(), vector<int>(2));
        for (int i = 0; i < strs.size(); i++) {
            for (char c : strs[i]) {
                arr[i][c - '0']++;
            }
        }

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

        for (const auto& pair : arr) {
            int zeros = pair[0], ones = pair[1];
            for (int j = m; j >= zeros; j--) {
                for (int k = n; k >= ones; k--) {
                    dp[j][k] = max(dp[j][k], 1 + dp[j - zeros][k - ones]);
                }
            }
        }

        return dp[m][n];
    }
};