Problem
Choose as many binary strings as possible without exceeding separate budgets for zeros and ones. Each string may be selected at most once. The practice version uses inclusive budget limits.
Worked examples
Input: strings = ["0","1","01"], zeros = 1, ones = 1
Output: 2
Choose "0" and "1", instead of selecting only "01".
Hints
Hint 1
This is a knapsack problem with two capacities.
Solution approach
- Count zeros and ones in each string. Maintain dp[z][o], the best count within both budgets.
- For each string, iterate both budgets downward before updating dp[z][o] from dp[z-zeroCount][o-oneCount] + 1.
- Descending iteration prevents choosing the same string multiple times.
Complexity
O(total input characters + strings × zeroBudget × oneBudget) time; O(zeroBudget × oneBudget) space.
Report & practice notes
The candidate report uses strict “less than” wording. This version uses inclusive budgets; reduce a strict integer bound by one if matching that variant.
Read the candidate’s source report ↗