{x}
blog image

Ones and Zeroes

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 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

 

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

 

Constraints:

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] consists only of digits '0' and '1'.
  • 1 <= m, n <= 100

Solution Explanation for LeetCode 474: Ones and Zeroes

This problem asks to find the largest subset of binary strings from a given array strs such that the total count of '0's and '1's in the subset does not exceed m and n respectively. This can be efficiently solved using dynamic programming.

Approach: Dynamic Programming

The core idea is to build a 3D DP table f[i][j][k], where:

  • i represents the index of the string being considered (from 0 to len(strs)).
  • j represents the number of '0's used so far (from 0 to m).
  • k represents the number of '1's used so far (from 0 to n).

f[i][j][k] stores the maximum size of a subset considering strings up to index i with at most j '0's and k '1's.

The DP relation is:

f[i][j][k] = max(f[i-1][j][k], f[i-1][j-zeros][k-ones] + 1)

where zeros and ones are the counts of '0's and '1's in strs[i-1]. We take the maximum of either not including strs[i-1] in the subset (using f[i-1][j][k]) or including it (if there are enough '0's and '1's remaining, using f[i-1][j-zeros][k-ones] + 1).

Solution 1 (3D DP): This solution directly implements the 3D DP relation described above. The base case is f[0][j][k] = 0 for all j and k. The final answer is stored in f[len(strs)][m][n].

Solution 2 (Optimized 2D DP): This solution optimizes the space complexity by observing that we only need the previous row of the 3D DP table to compute the current row. Thus, we can reduce the DP table to 2D (f[j][k]). The iterations are done in reverse order to avoid overwriting values needed in the current computation. The logic is the same as Solution 1, just with a more efficient use of space.

Time and Space Complexity Analysis

Solution 1 (3D DP):

  • Time Complexity: O(len(strs) * m * n). We iterate through the DP table once.
  • Space Complexity: O(len(strs) * m * n). We use a 3D DP table.

Solution 2 (Optimized 2D DP):

  • Time Complexity: O(len(strs) * m * n). The time complexity remains the same.
  • Space Complexity: O(m * n). We use a 2D DP table. This is a significant space optimization compared to Solution 1.

Code Examples (Python - Solution 2)

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for s in strs:
            a, b = s.count("0"), s.count("1")
            for i in range(m, a - 1, -1):
                for j in range(n, b - 1, -1):
                    f[i][j] = max(f[i][j], f[i - a][j - b] + 1)
        return f[m][n]

This Python code implements the optimized 2D DP solution. It's concise and efficient. Similar optimizations can be applied to other languages (Java, C++, Go, TypeScript) as shown previously. The core logic remains consistent across all languages.