# 3119. Maximum Number of Potholes That Can Be Fixed ðŸ”’

## Description

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 n consecutive 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(\text{budget} / (k + 1), \text{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$.

• class Solution {
public int maxPotholes(String road, int budget) {
int n = road.length();
int[] cnt = new int[n];
int k = 0;
for (char c : road.toCharArray()) {
if (c == 'x') {
++k;
} else if (k > 0) {
++cnt[k];
k = 0;
}
}
int ans = 0;
for (k = n - 1; k > 0 && budget > 0; --k) {
int t = Math.min(budget / (k + 1), cnt[k]);
ans += t * k;
budget -= t * (k + 1);
cnt[k - 1] += cnt[k] - t;
}
return ans;
}
}

• class Solution {
public:
int maxPotholes(string road, int budget) {
int n = road.size();
vector<int> cnt(n);
int k = 0;
for (char& c : road) {
if (c == 'x') {
++k;
} else if (k) {
++cnt[k];
k = 0;
}
}
int ans = 0;
for (k = n - 1; k && budget; --k) {
int t = min(budget / (k + 1), cnt[k]);
ans += t * k;
budget -= t * (k + 1);
cnt[k - 1] += cnt[k] - t;
}
return ans;
}
};

• class Solution:
def maxPotholes(self, road: str, budget: int) -> int:
cnt = [0] * n
k = 0
for c in road:
if c == "x":
k += 1
elif k:
cnt[k] += 1
k = 0
ans = 0
for k in range(n - 1, 0, -1):
if cnt[k] == 0:
continue
t = min(budget // (k + 1), cnt[k])
ans += t * k
budget -= t * (k + 1)
if budget == 0:
break
cnt[k - 1] += cnt[k] - t
return ans


• func maxPotholes(road string, budget int) (ans int) {
cnt := make([]int, n)
k := 0
for _, c := range road {
if c == 'x' {
k++
} else if k > 0 {
cnt[k]++
k = 0
}
}
for k = n - 1; k > 0 && budget > 0; k-- {
t := min(budget/(k+1), cnt[k])
ans += t * k
budget -= t * (k + 1)
cnt[k-1] += cnt[k] - t
}
return
}

• function maxPotholes(road: string, budget: number): number {
const n = road.length;
const cnt: number[] = Array(n).fill(0);
let k = 0;
for (const c of road) {
if (c === 'x') {
++k;
} else if (k) {
++cnt[k];
k = 0;
}
}
let ans = 0;
for (k = n - 1; k && budget; --k) {
const t = Math.min(Math.floor(budget / (k + 1)), cnt[k]);
ans += t * k;
budget -= t * (k + 1);
cnt[k - 1] += cnt[k] - t;
}
return ans;
}


• public class Solution {
public int MaxPotholes(string road, int budget) {
int n = road.Length;
int[] cnt = new int[n];
int k = 0;
foreach (char c in road) {
if (c == 'x') {
++k;
} else if (k > 0) {
++cnt[k];
k = 0;
}
}
int ans = 0;
for (k = n - 1; k > 0 && budget > 0; --k) {
int t = Math.Min(budget / (k + 1), cnt[k]);
ans += t * k;
budget -= t * (k + 1);
cnt[k - 1] += cnt[k] - t;
}
return ans;
}
}

• impl Solution {
pub fn max_potholes(road: String, budget: i32) -> i32 {
let mut cs: Vec<char> = road.chars().collect();
cs.push('.');
let n = cs.len();
let mut cnt: Vec<i32> = vec![0; n];
let mut k = 0;

for c in cs.iter() {
if *c == 'x' {
k += 1;
} else if k > 0 {
cnt[k] += 1;
k = 0;
}
}

let mut ans = 0;
let mut budget = budget;

for k in (1..n).rev() {
if budget == 0 {
break;
}
let t = std::cmp::min(budget / ((k as i32) + 1), cnt[k]);
ans += t * (k as i32);
budget -= t * ((k as i32) + 1);
cnt[k - 1] += cnt[k] - t;
}

ans
}
}