Show problems as
Classic problem #474MediumArrayStringDynamic ProgrammingKnapsack Problem0-1 Knapsack

Ones and Zeroes

Real-world version: Stamping the Most Part Codes
Tracked in this browser only
Read Ones and Zeroes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstKnapsack Problems · Dynamic Programming, animated step by step

A workshop marks parts with codes written only from the digits '0' and '1'. The list codes holds the codes waiting to be marked; the same code may appear more than once, and each entry in the list may be stamped at most once.

The tray holds zeros zero-stamps and ones one-stamps. Stamping a code consumes one stamp per digit of that code, of the matching kind, and every stamp is single use. A code counts only when all of its digits are stamped.

Return the largest number of entries from codes that can be stamped in full with the stamps in the tray.

Examples

Example 1

Input
codes = ["01", "0", "1"], zeros = 1, ones = 1
Output
2

Stamping `"0"` uses the zero-stamp and stamping `"1"` uses the one-stamp, which finishes two entries. The tray is then empty.

Example 2

Input
codes = ["11"], zeros = 1, ones = 1
Output
0

The only code needs two one-stamps and the tray holds one, so no entry can be finished.

Example 3

Input
codes = ["0000", "1111"], zeros = 3, ones = 4
Output
1

The four one-stamps cover `"1111"` exactly. `"0000"` needs four zero-stamps and only three are in the tray.

Constraints

  • 1 <= codes.length <= 600
  • 1 <= codes[i].length <= 100
  • 1 <= zeros, ones <= 100
  • Each code is made only of the digits '0' and '1'.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def most_codes(codes: list[str], zeros: int, ones: int) -> int:
Java
public int mostCodes(String[] codes, int zeros, int ones)

More on the same topics