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.

Largest Subset of Binary Strings Within Zero and One Budgets

Hints

1. Only how many '0's and how many '1's a string contains matters; the order of its characters is irrelevant.
2. Each position in strs is a separate element that may be chosen at most once, even when two strings are equal.
3. A string that by itself needs more zeros than max_zeros or more ones than max_ones can never be part of a valid subset.

Approach

Only the number of '0's and '1's in a string matters, so each string is an item with a two-dimensional cost (zeros, ones) and value 1, and the task is a 0/1 knapsack with two capacities. Keep a table best[i][j] = the largest number of strings, among those processed so far, whose combined counts are at most i zeros and at most j ones. Initially every entry is 0 (the empty subset is always valid). For each string with z zeros and o ones that fits on its own, set best[i][j] = max(best[i][j], best[i - z][j - o] + 1) for every i >= z and j >= o, sweeping i and j from high to low so that best[i - z][j - o] still holds the value from before this string was considered; this keeps each element to a single use even when z or o is 0. Invariant: after processing a prefix of strs, best[i][j] is the optimum for that prefix under budgets (i, j), because the update is exactly the choice between skipping and taking the current string. The answer is best[max_zeros][max_ones]. Edge cases: a string that alone exceeds either budget is skipped; a zero budget admits only strings with none of that character; equal strings at different positions are separate items; if nothing fits the answer is 0. Greedy rules such as shortest-first or fewest-of-one-character-first are not optimal.

• Time complexity: O(L + n * max_zeros * max_ones), where n = len(strs) and L is the total length of all strings
• Space complexity: O(max_zeros * max_ones)