725. Zeros and Ones Budget
A radio operator stores messages written in two kinds of beeps, short ones shown as '0' and long ones shown as '1'. Each message is a string in strs. The transmitter's battery lasts for at most m short beeps and at most n long beeps in total.
Return the largest number of different messages from strs that can all be sent without exceeding either budget. Each message can be sent at most once, and the two budgets are counted separately across all chosen messages. Sending nothing is allowed, so the answer is never negative.
Aim for time O(L * m * n) for L messages and space O(m * n).
Example 1
- Input:
- strs = ["011","00","1","110","0001"], m = 4, n = 3
- Output:
- 3
- Explanation:
The messages 011, 00 and 1 use 3 zeros and 3 ones, within the budget of 4 and 3, and no choice of four messages fits.
Example 2
- Input:
- strs = ["10","01","1100"], m = 1, n = 1
- Output:
- 1
- Explanation:
Only one of the two-beep messages fits, because both together would need 2 zeros and 2 ones.
Constraints
1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 20, each string contains only the characters 0 and 1
0 ≤ m, n ≤ 60
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(L * m * n)
- Space
- O(m * n)