Medium

Quiz

#474 Ones and Zeroes

APPROACH

You are given an array of binary strings strs and two integers m and n. Find the largest subset of strs such that the total number of '0''s across all chosen strings is at most m and the total number of '1''s is at most n. Return the size of that largest subset.

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.

1 of 4

1:00

What is the optimal approach for this problem?