Ones And Zeroes - Leetcode Solution

Problem Statement:

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:

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.

Solution Approach:

The main idea of this problem is to use dynamic programming where we create a 3-D matrix and store the maximum number of strings that can be formed with the given constraints of m and n.

The dimensions of the matrix will be (m+1) * (n+1) * (strs.length + 1) to represent the maximum string count for each possible value of m, n and each string in the array.

Initially, we will set the values of the matrix to zero.

Then, we will iterate through the array and for each string, we will count the number of 0s and 1s in it.

If the count of 0s and 1s in the current string is less than or equal to m and n respectively, then we will update the matrix.

We will update the matrix with the maximum value between the current cell and the cell obtained by adding the current string to the maximum subset at (m-count of 0s, n-count of 1s).

Finally, we will return the value at the last cell (m, n, strs.length).

Code:

Java Code:

public int findMaxForm(String[] strs, int m, int n) { int[][][] dp = new int[m+1][n+1][strs.length+1]; for(int i=0; i<=m; i++){ for(int j=0; j<=n; j++){ for(int k=0; k<=strs.length; k++){ if(i==0 && j==0){ dp[i][j][k] = 0; }else{ int zeros = countZeros(strs[k-1]); int ones = countOnes(strs[k-1]); if(k==0 || i<zeros || j<ones){ dp[i][j][k] = dp[i][j][k-1]; }else{ dp[i][j][k] = Math.max(dp[i][j][k-1], dp[i-zeros][j-ones][k-1]+1); } } } } } return dp[m][n][strs.length]; }

private int countZeros(String str){ int count = 0; for(char ch : str.toCharArray()){ if(ch=='0') count++; } return count; }

private int countOnes(String str){ int count = 0; for(char ch : str.toCharArray()){ if(ch=='1') count++; } return count; }

Python Code:

def findMaxForm(self, strs: List[str], m: int, n: int) -> int: dp = [[[0]*(len(strs)+1) for _ in range(n+1)] for _ in range(m+1)] for i in range(m+1): for j in range(n+1): for k in range(len(strs)+1): if i==0 and j==0: dp[i][j][k] = 0 else: zeros = self.countZeros(strs[k-1]) ones = self.countOnes(strs[k-1]) if k==0 or i<zeros or j<ones: dp[i][j][k] = dp[i][j][k-1] else: dp[i][j][k] = max( dp[i][j][k-1], dp[i-zeros][j-ones][k-1]+1) return dp[m][n][len(strs)]

def countZeros(self, str): count = 0 for ch in str: if ch=='0': count += 1 return count

def countOnes(self, str): count = 0 for ch in str: if ch=='1': count += 1 return count

Time Complexity: O(mnlen(strs))

Space Complexity: O(mnlen(strs))

1