Problem

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.

Examples

Example 1:

1
2
3
4

Input: road = "..", budget = 5
Output: 0
Explanation:
There are no potholes to be fixed.

Example 2:

1
2
3
4
5

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:

1
2
3
4
5

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 <= 10^5
  • 1 <= budget <= 10^5 + 1
  • road consists only of characters '.' and 'x'.

Solution

Method 1 – Greedy Group Repair

Intuition

To maximize the number of potholes fixed within the budget, we should repair the smallest groups of consecutive potholes first, as their cost per pothole is lower. By sorting all groups of consecutive potholes by their size, we can greedily fix as many as possible.

Approach

  1. Parse the road string to find all groups of consecutive ‘x’ (potholes) and record their lengths.
  2. Sort these group lengths in ascending order.
  3. For each group, try to fix the entire group if the budget allows (cost = group size + 1).
  4. If the budget is not enough for the whole group, fix as many potholes as possible individually (each costs 2).
  5. Stop when the budget runs out.
  6. Return the total number of potholes fixed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxPotholesFixed(string road, int budget) {
        vector<int> groups;
        int n = road.size(), cnt = 0, ans = 0;
        for (int i = 0; i <= n; ++i) {
            if (i < n && road[i] == 'x') cnt++;
            else if (cnt > 0) { groups.push_back(cnt); cnt = 0; }
        }
        sort(groups.begin(), groups.end());
        for (int g : groups) {
            int cost = g + 1;
            if (budget >= cost) { ans += g; budget -= cost; }
            else {
                int canFix = min(g, budget / 2);
                ans += canFix;
                break;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func maxPotholesFixed(road string, budget int) int {
    groups := []int{}
    cnt, ans := 0, 0
    for i := 0; i <= len(road); i++ {
        if i < len(road) && road[i] == 'x' {
            cnt++
        } else if cnt > 0 {
            groups = append(groups, cnt)
            cnt = 0
        }
    }
    sort.Ints(groups)
    for _, g := range groups {
        cost := g + 1
        if budget >= cost {
            ans += g
            budget -= cost
        } else {
            canFix := g
            if budget/2 < g {
                canFix = budget / 2
            }
            ans += canFix
            break
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int maxPotholesFixed(String road, int budget) {
        List<Integer> groups = new ArrayList<>();
        int cnt = 0, ans = 0, n = road.length();
        for (int i = 0; i <= n; i++) {
            if (i < n && road.charAt(i) == 'x') cnt++;
            else if (cnt > 0) { groups.add(cnt); cnt = 0; }
        }
        Collections.sort(groups);
        for (int g : groups) {
            int cost = g + 1;
            if (budget >= cost) { ans += g; budget -= cost; }
            else {
                int canFix = Math.min(g, budget / 2);
                ans += canFix;
                break;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun maxPotholesFixed(road: String, budget: Int): Int {
        val groups = mutableListOf<Int>()
        var cnt = 0
        var ans = 0
        for (i in 0..road.length) {
            if (i < road.length && road[i] == 'x') cnt++
            else if (cnt > 0) { groups.add(cnt); cnt = 0 }
        }
        groups.sort()
        var b = budget
        for (g in groups) {
            val cost = g + 1
            if (b >= cost) { ans += g; b -= cost }
            else {
                val canFix = minOf(g, b / 2)
                ans += canFix
                break
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def maxPotholesFixed(self, road: str, budget: int) -> int:
        groups: list[int] = []
        cnt: int = 0
        ans: int = 0
        n: int = len(road)
        for i in range(n + 1):
            if i < n and road[i] == 'x':
                cnt += 1
            elif cnt > 0:
                groups.append(cnt)
                cnt = 0
        groups.sort()
        for g in groups:
            cost = g + 1
            if budget >= cost:
                ans += g
                budget -= cost
            else:
                can_fix = min(g, budget // 2)
                ans += can_fix
                break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn max_potholes_fixed(road: String, mut budget: i32) -> i32 {
        let mut groups = vec![];
        let mut cnt = 0;
        let mut ans = 0;
        let n = road.len();
        let chars: Vec<char> = road.chars().collect();
        for i in 0..=n {
            if i < n && chars[i] == 'x' {
                cnt += 1;
            } else if cnt > 0 {
                groups.push(cnt);
                cnt = 0;
            }
        }
        groups.sort();
        for g in groups {
            let cost = g + 1;
            if budget >= cost {
                ans += g;
                budget -= cost;
            } else {
                let can_fix = std::cmp::min(g, budget / 2);
                ans += can_fix;
                break;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    maxPotholesFixed(road: string, budget: number): number {
        const groups: number[] = [];
        let cnt = 0, ans = 0;
        for (let i = 0; i <= road.length; i++) {
            if (i < road.length && road[i] === 'x') cnt++;
            else if (cnt > 0) { groups.push(cnt); cnt = 0; }
        }
        groups.sort((a, b) => a - b);
        for (const g of groups) {
            const cost = g + 1;
            if (budget >= cost) { ans += g; budget -= cost; }
            else {
                const canFix = Math.min(g, Math.floor(budget / 2));
                ans += canFix;
                break;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — We scan the road string once (O(n)) and sort the group sizes (O(k log k), where k is the number of groups, k <= n).
  • 🧺 Space complexity: O(n) — We store all group sizes, which in the worst case is up to n.