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:
class Solution:
    def longest(self, strs, i, m, n, slen):
        if m < 0 or n < 0:
            return -1
        if i >= slen:
            return 0
        key = (i, m, n)
        if key in self.cache:
            return self.cache[key]
        x, y = strs[i]
        a = 1 + self.longest(strs, i + 1, m - x, n - y, slen)
        b = self.longest(strs, i + 1, m, n, slen)
        mlen = max(a, b)
        self.cache[key] = mlen
        return mlen
    
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        slen = len(strs)
        strs = [(s.count("0"), s.count("1")) for s in strs]
        self.cache = {}
        return self.longest(strs, 0, m, n, slen)

Comments

Post a Comment

Popular posts from this blog

Minimum Number of Operations to Move All Balls to Each Box

You have n boxes. You are given a binary string boxes of length n , where boxes[i] is '0' if the i th box is empty , and '1' if it contains one ball. In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1 . Note that after doing so, there may be more than one ball in some boxes. Return an array answer of size n , where answer[i] is the minimum number of operations needed to move all the balls to the i th box. Each answer[i] is calculated considering the initial state of the boxes.   Example 1: Input: boxes = "110" Output: [1,1,3] Explanation: The answer for each box is as follows: 1) First box: you will have to move one ball from the second box to the first box in one operation. 2) Second box: you will have to move one ball from the first box to the second box in one operation. 3) Third box: you will have to move one ball from the first box to the third box in two...
Read more

Efficient Generation of Nth Row of Binomial Coefficient Modulo M

Efficient Generation of Nth Row of Binomial Coefficient Modulo M Efficient Generation of Nth Row of Binomial Coefficient Modulo M Introduction Calculating the binomial coefficient (also known as the combinatorial coefficient) is a common task in mathematics and programming. However, when the modulo M is not prime, finding an efficient method becomes more challenging. In this article, we will explore a technique that allows us to efficiently generate the Nth row of the binomial coefficient modulo M, even when M is not necessarily prime. This technique utilizes prime factorization and a sieve algorithm to achieve efficient computation. The Implementation Let's take a look at the implementation of the technique: from collections import Counter N = 1 + 10 ** 6 v = [False] * N spf = [1] * N for i in range(2, N, 2): spf[i] = 2 for i in range(3, N, 2): if not v[i]: spf[i] = i j = i while j * i 1: ctr[spf[a]...
Read more

Power of Two Difference

Power of Two Difference Power of Two Difference Problem Description Given an integer n , return true if it is a possible difference between powers of two. Otherwise, return false . An integer n is a difference between powers of two if there exist two integers x and y , where x >= y >= 0 , such that n == 2^x - 2^y . Solution Approach The problem can be solved using an elegant solution. We can observe that if n = 2^x - 2^y , then n = 2^y * (2^(x-y) - 1) . Let's call y as M and x - y as N . Now, we observe that 2^N - 1 is a binary number of the form 111...111 , where 1 is repeated N times. Multiplying a binary number by 2^M will add 0 M times to the right. Therefore, our result is of the form 11...1100...00 , where 1 is repeated some times followed by 0 repeated some times or 0 times. For example, 0 is true, 7 is true because it's 111, 12 is true because it's 1100, whereas 5 is false because it's 101 and 13 is false because it's 1101. ...
Read more