Max Potholes Repaired
MediumGreedy · Microsoft
A road is described by a string road, where each character is one segment: "x" is a pothole and "." is a smooth segment.
A repair crew can fix a contiguous stretch of potholes in one job: the stretch must consist only of "x" segments that are next to each other (it may be part of a longer run of potholes). Fixing a stretch of L potholes costs L + 1.
Given a total budget, return the maximum number of potholes that can be fixed.
Example 1
- Input:
- road = "xx.xxxx..x.xxx", budget = 9
- Output:
- 7
- Explanation
- The pothole runs have lengths 2, 4, 1 and 3. Fixing the run of 4 costs 5, leaving 4, which fixes the run of 3 exactly. That repairs 7 potholes.
Example 2
- Input:
- road = "..xxxxxx.", budget = 5
- Output:
- 4
- Explanation
- There is one run of 6, but the budget of 5 only pays for a stretch of 4 (cost
4 + 1).
Example 3
- Input:
- road = "x.x.x", budget = 1
- Output:
- 0
- Explanation
- Even a single pothole costs 2, so nothing can be fixed.
Constraints
1 <= road.length <= 10^5roadcontains only"x"and"."0 <= budget <= 2 * 10^5