You are given a string road, consisting only of characters "x" and ".", where each "x" denotes a pothole and each "." denotes a smooth road, and an integer budget.
In one repair operation, you can repair nconsecutive potholes for a price of n + 1.
Return the maximum number of potholes that can be fixed such that the sum of the prices of all of the fixes doesn't go over the given budget.
Example 1:
Input:road = "..", budget = 5
Output:0
Explanation:
There are no potholes to be fixed.
Example 2:
Input:road = "..xxxxx", budget = 4
Output:3
Explanation:
We fix the first three potholes (they are consecutive). The budget needed for this task is 3 + 1 = 4.
Example 3:
Input:road = "x.x.xxx...x", budget = 14
Output:6
Explanation:
We can fix all the potholes. The total cost would be (1 + 1) + (1 + 1) + (3 + 1) + (1 + 1) = 10 which is within our budget of 14.
Constraints:
1 <= road.length <= 105
1 <= budget <= 105 + 1
road consists only of characters '.' and 'x'.
Solutions
Solution 1: Counting + Greedy
First, we count the number of each continuous pothole, recorded in the array $cnt$, i.e., $cnt[k]$ represents there are $cnt[k]$ continuous potholes of length $k$.
Since we want to repair as many potholes as possible, and for a continuous pothole of length $k$, we need to spend a cost of $k + 1$, we should prioritize repairing longer potholes to minimize the cost.
Therefore, we start repairing from the longest pothole. For a pothole of length $k$, the maximum number we can repair is $t = \min(\textit{budget} / (k + 1), \textit{cnt}[k])$. We add the number of repairs multiplied by the length $k$ to the answer, then update the remaining budget. For the remaining $cnt[k] - t$ potholes of length $k$, we merge them into the potholes of length $k - 1$. Continue this process until all potholes are traversed.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string $road$.