Maximize the number of binary strings chosen under zero and one budgets
Company: Amazon
Role: Frontend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Given a list of binary strings and separate limits on the total number of zeros and ones, find the largest number of strings that can be chosen together without exceeding either limit. Tests optimization under two simultaneous resource limits, moving from brute force to an efficient method, and complexity analysis.
Read the full Amazon Frontend Engineer interview experience this question came from
You are given a list `strs` of binary strings (each made only of the characters '0' and '1') and two budgets, `max_zeros` and `max_ones`. Choose a subset of the strings such that, counted over all chosen strings together, there are at most `max_zeros` characters '0' and at most `max_ones` characters '1'. Return the largest possible number of strings in such a subset.
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 (a single integer), not the subset itself.
Example 1:
Input: strs = ["01", "0", "110", "1", "0011"], max_zeros = 3, max_ones = 2
Output: 3
Explanation: 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
Explanation: Only one "1" fits in the ones budget, and "0" needs a zero that the budget does not allow.
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
The answer is at most len(strs) <= 600 and no count of characters exceeds 60,000, so no value exceeds 2^31 - 1; a 32-bit int is sufficient in every language.
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
- The answer is at most len(strs), so every value fits in a 32-bit signed integer
Examples
Input: (['01', '0', '110', '1', '0011'], 3, 2)
Expected Output: 3
Explanation: Source Example 1: '0', '01', '1' use 2 zeros and 2 ones; any 4 strings need at least 4 ones.
Input: (['1', '1', '0'], 0, 1)
Expected Output: 1
Explanation: Source Example 2: only one '1' fits the ones budget and '0' needs a forbidden zero.
Hints
- Only how many '0's and how many '1's a string contains matters; the order of its characters is irrelevant.
- Each position in strs is a separate element that may be chosen at most once, even when two strings are equal.
- 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.