Maximize the number of binary strings chosen under zero and one budgets

You are given a list of binary strings and two budgets: at most max_zeros characters '0' and at most max_ones characters '1' in total. Choose a subset of the strings such that, counted over all chosen strings together, there are at most max_zeros zeros and at most max_ones ones. Return the largest possible number of strings in such a subset.

Function Signature

def largest_subset(strs: list[str], max_zeros: int, max_ones: int) -> int:

Rules

• Each element of strs can be chosen at most once. Equal strings at different positions are different elements, and both can be chosen.
• The empty subset is always allowed, so the answer is at least 0.
• Return only the size of a largest valid subset, not the subset itself.

Constraints

• 1 <= len(strs) <= 600
• 1 <= len(strs[i]) <= 100, and each strs[i] consists only of '0' and '1'
• 0 <= max_zeros <= 100
• 0 <= max_ones <= 100

Examples

Example 1

Input: strs = ["01", "0", "110", "1", "0011"], max_zeros = 3, max_ones = 2
Output: 3

Choosing "0", "01" and "1" uses 2 zeros and 2 ones. The five strings contain 6 ones in total, and leaving out any single string still leaves at least 4 ones, so no 4 strings fit.

Example 2

Input: strs = ["1", "1", "0"], max_zeros = 0, max_ones = 1
Output: 1

Only one "1" fits in the ones budget, and "0" needs a zero that the budget does not allow.

Example 3

Input: strs = ["111", "000"], max_zeros = 2, max_ones = 2
Output: 0

Each string on its own exceeds one of the budgets, so only the empty subset is valid.