All problems

Ones and Zeroes

Medium · dynamic programming

You are given a list strs of non-empty strings made only of the characters "0" and "1", and two budgets: zeros and ones.

You may pick some of the strings, each at most once. The strings you pick must together contain at most zeros characters "0" and at most ones characters "1".

Return the largest number of strings you can pick. If no string fits, return 0.

Examples

Example 1

Input: strs = ["01", "001", "110", "1", "0"], zeros = 3, ones = 3

Output: 3

Picking "01", "1" and "0" uses 2 zeros and 2 ones, and no fourth string fits in what is left.

Example 2

Input: strs = ["11", "11"], zeros = 0, ones = 1

Output: 0

Each string needs two ones, but only one is allowed.

Example 3

Input: strs = ["0", "0", "0"], zeros = 2, ones = 0

Output: 2

Two of the three single-zero strings fit.

Constraints

• 1 <= len(strs) <= 200
• 1 <= len(strs[i]) <= 20, and every character is "0" or "1".
• 0 <= zeros <= 60
• 0 <= ones <= 60