Fence Repair Run
Medium · sliding window
A village fence is made of planks in a row. The list damage describes them: damage[i] is the cost of repairing plank i, written as a whole number. A plank that is already sound has a cost of 0 and needs no repair.
A carpenter has a limited day. He can repair at most k planks in total, and the repairs he makes must cost at most budget altogether. Planks he does not repair stay as they are.
He wants to walk away with the longest possible run of neighbouring planks, with none skipped, in which every plank is sound once he has finished. Planks outside the run do not matter.
Return the number of planks in the longest run he can make sound. If no run can be made sound, return 0.
Examples
Example 1
Input: damage = [0, 4, 0, 0, 3, 5, 0], k = 2, budget = 7
Output: 5
Planks 0 to 4 hold two damaged planks costing 4 and 3, which is exactly 7. Adding plank 5 would need a third repair.
Example 2
Input: damage = [6, 6], k = 1, budget = 5
Output: 0
Each plank costs more than the whole budget.
Example 3
Input: damage = [1, 1, 1, 1], k = 2, budget = 10
Output: 2
The budget is plentiful, but he can only repair two planks.
Constraints
- 1 <= len(damage) <= 10^5
- 0 <= damage[i] <= 10^4
- 0 <= k <= 10^5
- 0 <= budget <= 10^9