Bit Budget Selection
Medium2-D Dynamic Programming
Problem
A test fixture can store a limited number of 0 bits and 1 bits. You are given candidate binary codewords words; storing a codeword consumes exactly as many 0s and 1s as it contains.
Return the largest number of codewords you can store at once without exceeding zeros zero-bits and ones one-bits. Each codeword can be stored at most once.
Example 1
- Input:
- words = ["10", "0001", "111001", "1", "0"], zeros = 5, ones = 3
- Output:
- 4
"10", "0001", "1" and "0" use 5 zeros and 3 ones in total. "111001" alone already needs 4 ones.
Example 2
- Input:
- words = ["10", "0", "1"], zeros = 1, ones = 1
- Output:
- 2
"0" and "1" together; "10" alone would fill both budgets.
Constraints
- 1 ≤ words.length ≤ 300
- 1 ≤ words[i].length ≤ 100
- words[i] contains only '0' and '1'
- 0 ≤ zeros, ones ≤ 100
Hint
Show the first hint
This is a backpack with two independent capacity limits instead of one.
Walkthrough
How to approach it
01Clarify before coding
- Do the budgets have to be used fully? No, they are upper limits.
- Can the same codeword string appear twice in the list? Yes; each copy is a separate item.
- Is the 'value' of each codeword equal? Yes, we maximise the count, so each item is worth 1.
02Brute force
Try every subset of codewords, count its zeros and ones, and keep the largest subset within both budgets.
Cost: O(2^n · L) for n words of length L: unthinkable for n = 300.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.