Problem statement

https://leetcode.com/problems/ones-and-zeroes/

Solution

Actually, what is asked: let as have $k$ pairs $(x_1, y_1), \dots , (x_k, y_k)$. We need to answer, how many of them we can choose, so sum of all chosen $x$ less than $m$ and sum of all chosen $y$ is less than $n$. One way to solve it is to use dp(mm, nn, kk), where:

  1. mm is how many zeroes we still allowed to take
  2. nn is how many ones we still allowed to take
  3. kk is how many pairs our of k we already processed

Then what we can do is the following:

  1. if mm < 0 or nn < 0, we return -1, because we take more zeroes or ones than allowed
  2. if kk = len(strs), it means, that we out of pairs, return 0.
  3. finally, we can have two options: either take the last pair or not, and we choose the maximum.

Complexity

Time and space complexity is $\mathcal{O}(mnk)$, where $k$ is number of strings, because we have this number of states and only 2 transitions from given state.

Code

class Solution:
    def findMaxForm(self, strs, m, n):
        xy = [[s.count("0"), s.count("1")] for s in strs]

        @lru_cache(None)
        
        def dp(mm, nn, kk):
            if mm < 0 or nn < 0: return -1
            if kk == len(strs): return 0
            x, y = xy[kk]
            return max(1 + dp(mm-x, nn-y, kk + 1), dp(mm, nn, kk + 1))
        
        return dp(m, n, 0)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0474