Ones and zeroes: most strings within zero and one budgets

You get a list of binary strings and two budgets: at most max_zeros zeros and at most max_ones ones in total. Choose as many strings as possible so that, counted over all chosen strings, both budgets hold. Return how many you can choose.

Interface

Unless you agree on a different interface with the interviewer, assume:

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

Example

largest_subset(["00", "1", "10", "011", "0"], 3, 2)  ->  3    # "1", "10", "0": 2 zeros, 2 ones
largest_subset(["11", "0"], 0, 1)                    ->  0    # each string breaks a budget
largest_subset(["1", "1", "1"], 0, 2)                ->  2    # equal strings are separate items

Constraints

• Up to 600 strings, each 1 to 100 characters; 0 <= max_zeros, max_ones <= 100.
• Each string can be chosen at most once.

Clarifying questions

• Can a string be chosen more than once?
• Do I return the count or the chosen strings?
• How large are the budgets? (That decides whether a table over both is affordable.)

What a strong answer covers

• Only each string's count of zeros and ones matters.
• Recognizing a 0/1 knapsack with two capacities: dp[z][o] is the most strings using at most z zeros and o ones.
• Iterating the budgets downward per string so each string is used once.
• O(len(strs) · max_zeros · max_ones) time and O(max_zeros · max_ones) space.
• Why greedy (shortest strings first) fails, with a counterexample.

Follow-ups

• Return the chosen strings, not just their count.
• Each string has a value; maximize the total value instead.
• The budgets are up to 10^5. What now?