Problem Statement in English

You’re given an array of binary strings strs and two integers m and n. You need to find the size of the largest subset of strs such that there are at most m 0’s and n 1’s in the subset.

Approach

The important thing to understand here is that there is no smart/greedy way to select the strings. We have to try out all possible combinations of strings to find the optimal solution.

What we can do to improve runtime is cache the results of subproblems using memoization.

The subproblems here are that at each string, we have two choices - either include it in our subset or exclude it. We can recursively explore both choices and keep track of the remaining counts of 0’s and 1’s we can use.

A neat trick that can be employed in such problems is to sort the strings in descending order of their total length (number of 0’s + number of 1’s). This way, we can try to include longer strings first, which allow us early exits in our recursive calls when we run out of 0’s or 1’s.

Solution in Python


class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        arr = []

        for s in strs:
            c = Counter(s)
            # overall count,count of 0, count of 1
            arr.append((c['0'] + c['1'], c['0'], c['1']))

        arr.sort(reverse=True)

        @cache
        def dfs(i, nm, nn):
            res = 0
            
            if i >= len(arr):
                return 0

            _, cm, cn = arr[i]

            include = exclude = 0 

            if cm <= nm and cn <= nn:
                include = dfs(i + 1, nm - cm, nn - cn) + 1
            exclude = dfs(i + 1, nm, nn)

            res = max(res, include, exclude)

            return res

        return dfs(0, m, n)

Complexity

  • Time: $O(m \times n \times l)$
    Here, m and n are the counts of 0’s and 1’s respectively, and l is the number of strings in strs. This is because we cache results for each combination of remaining 0’s and 1’s for each string.

  • Space: $O(m \times n \times l)$
    This is because of the space used up by the memoization cache.

Mistakes I Made

I made res global 🤦‍♂️

And we are done.