Two-resource pack: hints, no solution
Medium · 2-D dynamic programming
A tagging system stores each tag as a binary string of '0' and '1' characters, and tag i has a score of scores[i]. A batch can hold at most zeros characters '0' and at most ones characters '1' in total across all the tags chosen for it. Each tag can be chosen at most once. Return the maximum total score of a batch that respects both budgets. If no tag fits, return 0.
Examples
- Input
- tags = ["01", "110", "0", "1001", "11"], scores = [4, 7, 2, 9, 3], zeros = 3, ones = 3
- Output
- 13
- Note
- Choose the tags that best use both budgets.
- Input
- tags = ["000", "111"], scores = [5, 5], zeros = 2, ones = 2
- Output
- 0
- Note
- Each tag needs three of one character, and the budgets are two.
- Input
- tags = ["1", "0", "10"], scores = [3, 3, 5], zeros = 1, ones = 1
- Output
- 6
Constraints
- 0 <= tags.length <= 200, and scores has the same length
- 1 <= tags[i].length <= 20, characters are '0' or '1'
- 1 <= scores[i] <= 100, 0 <= zeros, ones <= 100
Hint 1: a nudge
Each tag spends from two separate budgets at once. What would you need to remember to know whether one more tag still fits?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.