474-ones-and-zeroes

Try it on leetcode

Description

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(Python)

from itertools import chain, combinations


class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        return self.topdowndp(strs, m, n)

    # Time Complexity : O(N*2^N)
    # Space Complexity: O(2^N)
    def bruteforce(self, strs: List[str], m: int, n: int) -> int:
        res = 0
        for subset in self.powerset(strs):
            zeros = sum([s.count("0") for s in subset])
            ones = sum([s.count("1") for s in subset])
            if zeros < m and ones < n:
                if len(subset) > res:
                    res = len(subset)
        return res

    def powerset(self, iterable):
        "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
        s = list(iterable)
        return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

    # Time Complexity : O(n*m*N)
    # Space Complexity: O(n*m*N)
    def topdowndp(self, strs: List[str], m: int, n: int) -> int:
        @cache
        def backtrack(m, n, i):
            if m < 0 or n < 0:
                return float("-inf")
            if i >= len(strs):
                return 0
            zero = 0
            one = 0
            for c in strs[i]:
                if c == "0":
                    zero += 1
                else:
                    one += 1
            include = 1 + backtrack(m - zero, n - one, i + 1)
            exclude = backtrack(m, n, i + 1)
            return max(include, exclude)

        return backtrack(m, n, 0)