474.-ones-and-zeroes.md

474. Ones and Zeroes

• Medium

• 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.

Analysis

The brute force solution would be to use backtrack. We can check the case for each string whether it is chosen or not. This will give us a O(2^N) solution.

So how can we improve that? We solve it using dynamic planning. In the following matrix dp, dp[i][j] represents the largest subset we can have with limits of i zeros and j ones. Each position can be derived from the previous state, dp[i-zeros][j-ones], where zeros is the number of 0s in the current string and ones is the number of 1s. Either we chose to add the current one, making it dp[i-zeros][j-ones]+1 or we keep it as it is, keeping dp[i][j].

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp=[[0 for _ in range(n+1)]for _ in range(m+1)]

        for string in strs:
            ones=0
            zeros=0
            for letter in string:
                if letter=="0":
                    zeros+=1
                else:
                    ones+=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]