Ones and Zeroes

Intuition

Each string is an item that costs a certain number of zeros and a certain number of ones, and picking it adds one to the subset size. This is a knapsack with two independent capacity dimensions instead of one. We keep a table dp[i][j] holding the maximum number of strings we can select while spending at most i zeros and j ones. For each string we update the table from high capacities down to low, which enforces that the string is used at most once. The final answer is dp[m][n].

Algorithm walkthrough

1. 1Initialize a (m + 1) by (n + 1) grid dp filled with zeros; dp[i][j] means the best subset size within i zeros and j ones.
2. 2For each string, count its zeros and ones.
3. 3Iterate i from m down to that string's zero-count and j from n down to its one-count, updating dp[i][j] with the larger of itself and dp[i - zeros][j - ones] + 1.
4. 4Sweeping both dimensions downward guarantees each string is added to any state at most once, preserving the 0/1 constraint.
5. 5After all strings are processed, return dp[m][n], the largest subset fitting both budgets.

Implementation

class Solution:
    def findMaxForm(self, 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], dp[i - zeros][j - ones] + 1)
        return dp[m][n]