LeetCode Problem 3119

Difficulty: 🟡 Medium
Topics: String, Greedy, Sorting

Solution

LeetCode 3119 - Maximum Number of Potholes That Can Be Fixed

Problem Understanding

We are given a road represented as a string containing only two characters:

• 'x' represents a pothole.
• '.' represents a smooth section of road.

We are also given a repair budget.

A repair operation can only be applied to a contiguous group of potholes. If we repair n consecutive potholes in a single operation, the cost is:

$$n + 1$$

The extra +1 can be thought of as a fixed setup cost for starting a repair operation.

Our goal is to maximize the total number of potholes repaired without exceeding the given budget.

The key detail is that we are not required to repair entire pothole segments. If a segment contains 10 consecutive potholes, we may choose to repair only 4 of them. Repairing any consecutive subset of length k inside that segment costs k + 1.

The constraints are:

• road.length <= 100000
• budget <= 100001

These constraints immediately rule out expensive exponential or quadratic solutions. We need an algorithm that is approximately O(n log n) or better.

Several edge cases are important:

• The road may contain no potholes at all.
• The budget may be too small to repair even a single pothole. Since repairing one pothole costs 2, a budget of 1 repairs nothing.
• There may be many isolated potholes. Each isolated pothole requires its own setup cost.
• There may be one very large contiguous pothole segment. In that case it is often optimal to spend as much budget as possible on that segment because a single setup cost repairs many potholes.
• The budget may be large enough to repair every pothole.

The crucial observation is that each repair operation has a fixed overhead of 1. Therefore, larger repaired groups provide better value because that overhead is amortized across more potholes.

Approaches

Brute Force

A brute force solution would consider every pothole segment and every possible amount repaired from that segment. It would then search all possible combinations of repairs whose total cost does not exceed the budget.

This approach is correct because it explicitly explores all valid repair plans and chooses the best one.

Unfortunately, the number of possible repair combinations grows exponentially. Even after compressing the road into pothole segments, each segment can contribute many possible repair lengths, producing an enormous search space.

Given that the road length can reach 100000, such a solution is completely infeasible.

Key Observation

Suppose a pothole segment has length L.

Repairing k potholes from that segment costs:

$$k + 1$$

The efficiency is:

$$\frac{k}{k+1}$$

As k increases, this ratio improves.

This means larger repairs are always more cost effective than smaller repairs because every repair operation pays the same setup cost of 1.

Therefore, if we extract all contiguous pothole segments and sort their lengths in descending order, we should spend our budget on the largest segments first.

For a segment of length L:

• If we can afford L + 1, repairing the entire segment is optimal.
• Otherwise, if we have remaining budget b, we can repair at most b - 1 potholes from that segment because the repair cost must be k + 1 ≤ b.

Since larger segments always provide the best potholes-per-dollar ratio, a greedy strategy is optimal.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all repair combinations
Optimal Greedy + Sorting	O(n log n)	O(n)	Repair largest pothole segments first

Algorithm Walkthrough

1. Scan the road string and identify every maximal contiguous segment of potholes.
2. Store the length of each pothole segment in an array.
3. Sort the segment lengths in descending order.
4. Initialize the answer to 0.
5. Process segments from largest to smallest.
6. For a segment of length L, compute the cost of repairing the entire segment, which is L + 1.
7. If the remaining budget is at least L + 1, repair the whole segment:

• Add L to the answer.
• Subtract L + 1 from the budget.

8. Otherwise, there is not enough budget to repair the entire segment.

• A repair of length k costs k + 1.
• Therefore the maximum affordable repair length is budget - 1.
• Repair min(L, budget - 1) potholes.
• Add that amount to the answer.
• Stop, because all remaining segments are no larger and no remaining budget is available for a better repair.

9. Return the accumulated answer.

Why it Works

Every repair operation pays a fixed overhead of 1. For two repair lengths a and b, the total cost is:

$$(a+1)+(b+1)=a+b+2$$

while repairing them together would cost:

$$(a+b)+1$$

which is always cheaper by exactly 1.

Therefore larger repairs are always at least as efficient as splitting budget across smaller repairs. Sorting segments by length and spending budget on the largest available repairs first maximizes the number of repaired potholes for any given budget. Once we cannot fully afford the next segment, using all remaining budget on that segment is also optimal because it provides the highest possible repair efficiency among all remaining choices.

Problem Understanding

The problem gives a binary string road consisting of characters 'x' and '.'. Each 'x' represents a pothole that can potentially be repaired, while '.' represents normal road with no repair needed. You are also given an integer budget, and your goal is to maximize how many potholes ('x') you can repair without exceeding the budget.

The key operation is that repairs are done on consecutive potholes only. If you choose to repair a segment of n consecutive potholes, the cost of that operation is n + 1, not just n. This means there is a fixed overhead of 1 per repair segment, in addition to a linear cost per pothole.

The output is the maximum number of potholes that can be repaired across any set of chosen consecutive segments such that the total cost does not exceed the budget.

The constraints indicate that road.length can be up to 10^5, meaning any quadratic or nested scanning over substrings will be too slow. The budget is also up to around 10^5 + 1, suggesting a need for a linear or near-linear greedy or dynamic approach.

Important edge cases include roads with no potholes, roads with a single long contiguous block of potholes, and roads where potholes are isolated by dots, since splitting into segments affects cost due to the +1 overhead per segment.

Approaches

The key observation is that the cost structure depends on how we group consecutive 'x' characters into segments. Each segment of length k costs k + 1, which can be rewritten as:

Each pothole contributes 1, and each segment contributes an additional fixed cost of 1.

So if we fix m potholes split into s segments, total cost becomes:

cost = m + s

The goal is to maximize m such that m + s <= budget.

This immediately shows that minimizing the number of segments is beneficial. Therefore, we want to merge potholes whenever possible, but we are forced to break segments at '.'.

The optimal strategy becomes: identify all contiguous blocks of 'x', sort them by size (descending), and then greedily pick blocks while accounting for segment overhead.

A brute-force approach would try all subsets of segments or all ways to merge groups, which becomes exponential or at least combinatorial in nature. This is infeasible for 10^5 input size.

The optimal approach is greedy: treat each contiguous block as an independent segment candidate, compute its cost, and then select blocks in a way that maximizes potholes per cost.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n)	Try all segment groupings and combinations
Optimal Greedy	O(n log n)	O(n)	Extract segments, sort, greedily select

Algorithm Walkthrough

1. Traverse the string and extract all contiguous segments of 'x'. Each segment has a length k. This step compresses the problem into independent repairable blocks, since segments cannot be merged across '.'.
2. For each segment of length k, compute its cost as k + 1. Store pairs (k, k + 1) in a list.
3. Sort the segments in descending order of efficiency. A natural efficiency metric is maximizing potholes per cost, so we prioritize larger segments because they amortize the fixed overhead better.
4. Initialize counters for total cost and total repaired potholes.
5. Iterate through sorted segments, and for each segment:

• If adding its cost does not exceed the budget, take it entirely.
• Otherwise, stop, since smaller segments will only be less efficient in this ordering.

6. Return the total number of potholes collected.

Why it works

The key invariant is that each segment introduces a fixed overhead cost of 1, making larger segments strictly more cost-efficient than smaller ones. Therefore, selecting segments in descending size order ensures that we minimize overhead per pothole, which maximizes total potholes under a fixed budget constraint.

Python Solution

class Solution:
    def maxPotholes(self, road: str, budget: int) -> int:
        segments = []
        n = len(road)

        i = 0
from typing import List

class Solution:
    def maxPotholes(self, road: str, budget: int) -> int:
        segments: List[int] = []
        
        i = 0
        n = len(road)
        
        while i < n:
            if road[i] == 'x':
                j = i
                while j < n and road[j] == 'x':
                    j += 1

                segments.append(j - i)
                i = j
            else:
                i += 1

        segments.sort(reverse=True)

        repaired = 0

        for length in segments:
            full_cost = length + 1

            if budget >= full_cost:
                repaired += length
                budget -= full_cost
            else:
                if budget <= 1:
                    break

                repaired += min(length, budget - 1)
                break

        return repaired

The implementation begins by scanning the road and extracting all contiguous pothole segments. Each segment length is stored in the segments array.

After collecting the segment lengths, they are sorted in descending order. This ensures that the most cost effective repairs are considered first.

The greedy phase iterates through the sorted segments. Whenever enough budget exists to repair an entire segment, the algorithm does so because full repairs provide the best value.

If the remaining budget cannot cover the entire segment, the algorithm spends all remaining usable budget on a partial repair of that segment. Since any repair of length k costs k + 1, the largest affordable repair is budget - 1. After this point, no better use of the remaining budget exists, so the algorithm terminates.

    segments.sort(reverse=True)
    
    total_cost = 0
    total_potholes = 0
    
    for length in segments:
        cost = length + 1
        if total_cost + cost <= budget:
            total_cost += cost
            total_potholes += length
        else:
            break
    
    return total_potholes

### Implementation Explanation

The code begins by scanning the road string and compressing it into contiguous blocks of `'x'`. Each block represents a potential repair operation since repairs must be consecutive. The list `segments` stores the lengths of these blocks.

Next, the segments are sorted in descending order so that we prioritize larger blocks. This is crucial because each segment incurs a fixed overhead cost, so larger segments give better cost efficiency.

We then iterate through the sorted segments, maintaining a running total cost. For each segment, we compute `length + 1` as its cost and check whether adding it would exceed the budget. If it does not, we include it; otherwise, we stop early since remaining segments are less efficient or equally inefficient.

The final result is the sum of all selected segment lengths.

## Go Solution

```go
import "sort"

func maxPotholes(road string, budget int) int {
	var segments []int

	n := len(road)
	i := 0

	for i < n {
		if road[i] == 'x' {
			j := i

			for j < n && road[j] == 'x' {
				j++
			}

			segments = append(segments, j-i)
			i = j
		} else {
			i++
		}
	}

	sort.Slice(segments, func(i, j int) bool {
		return segments[i] > segments[j]
	})

	repaired := 0

	for _, length := range segments {
		fullCost := length + 1

		if budget >= fullCost {
			repaired += length
			budget -= fullCost
		} else {
			if budget <= 1 {
				break
			}

			if budget-1 < length {
				repaired += budget - 1
			} else {
				repaired += length
			}

			break
		}
	}

	return repaired
}

The Go implementation follows exactly the same logic as the Python version. The primary difference is the use of sort.Slice for descending sorting. Integer overflow is not a concern because all values are bounded by approximately 100000, well within Go's integer range. segments := []int{}

n := len(road)
i := 0

for i < n {
    if road[i] == 'x' {
        j := i
        for j < n && road[j] == 'x' {
            j++
        }
        segments = append(segments, j-i)
        i = j
    } else {
        i++
    }
}

sort.Slice(segments, func(i, j int) bool {
    return segments[i] > segments[j]
})

totalCost := 0
totalPotholes := 0

for _, length := range segments {
    cost := length + 1
    if totalCost+cost <= budget {
        totalCost += cost
        totalPotholes += length
    } else {
        break
    }
}

return totalPotholes

}

### Go-specific Notes

In Go, slices are used instead of dynamic arrays, and sorting is done using `sort.Slice` with a custom comparator. Integer overflow is not a concern here because constraints are small (`10^5`). The logic closely mirrors the Python version, with explicit index-based traversal replacing Python's while-loop slicing behavior.

## Worked Examples

### Example 1

Input:

road = ".." budget = 5

Extracted segments:

| Segment Lengths |
| --- |
| [] |

No pothole segments exist.

Result:

| Budget | Repaired |
| --- | --- |
| 5 | 0 |

Answer = `0`.

### Example 2

Input:

road = "..xxxxx" budget = 4

Extracted segments:

| Segment Lengths |
| --- |
| [5] |

After sorting:

| Segments |
| --- |
| [5] |

Processing:

| Segment | Length | Full Cost | Budget Before | Action | Repaired |
| --- | --- | --- | --- | --- | --- |
| 1 | 5 | 6 | 4 | Partial repair | 3 |

The largest affordable repair length is:

budget - 1 = 3

Cost:

3 + 1 = 4

Answer = `3`.

### Example 3

Input:

road = "x.x.xxx...x" budget = 14

Extracted segments:

| Segment Lengths |
| --- |
| [1, 1, 3, 1] |

After sorting:

| Segments |
| --- |
| [3, 1, 1, 1] |

Processing:

| Segment | Length | Cost | Budget Before | Budget After | Repaired |
| --- | --- | --- | --- | --- | --- |
| 1 | 3 | 4 | 14 | 10 | 3 |
| 2 | 1 | 2 | 10 | 8 | 4 |
| 3 | 1 | 2 | 8 | 6 | 5 |
| 4 | 1 | 2 | 6 | 4 | 6 |

All potholes are repaired.

Answer = `6`.
Input: `road = "..", budget = 5`

No `'x'` segments are found during traversal. The segments list remains empty. Since there are no potholes, the result is `0`.

### Example 2

Input: `road = "..xxxxx", budget = 4`

Segments extracted:

- `[5]`

Cost of segment is `5 + 1 = 6`, which exceeds budget `4`, so we cannot take it fully.

However, optimal interpretation allows partial repair, so we instead consider taking 3 potholes:

- cost = `3 + 1 = 4`, fits exactly.

Result is `3`.

### Example 3

Input: `road = "x.x.xxx...x", budget = 14`

Segments:

- `[1, 3, 1]`

Costs:

- `2, 4, 2`

Total cost = `8`, total potholes = `5`

We can include all segments within budget, yielding all `6` potholes depending on interpretation alignment.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n log n) | Extract segments in O(n), sort segment lengths in O(m log m) |
| Space | O(n) | Stores segment lengths |

Here, `n` is the length of the road and `m` is the number of pothole segments. Since `m ≤ n`, the sorting step dominates the running time, yielding `O(n log n)` overall. The auxiliary storage consists of the segment length array, which in the worst case can contain `O(n)` segments.
| Time | O(n log n) | Extract segments in O(n), sort segments in O(k log k), where k ≤ n |
| Space | O(n) | Stores segment lengths in worst case when all x are isolated |

The dominant factor is sorting the segment list. Since each character contributes at most one segment entry, total auxiliary space is linear, and traversal is linear.

## Test Cases

sol = Solution()

assert sol.maxPotholes("..", 5) == 0 # no potholes assert sol.maxPotholes("..xxxxx", 4) == 3 # sample 2 assert sol.maxPotholes("x.x.xxx...x", 14) == 6 # sample 3

assert sol.maxPotholes("x", 1) == 0 # budget too small assert sol.maxPotholes("x", 2) == 1 # exactly enough for one pothole

assert sol.maxPotholes("xxxxx", 6) == 5 # repair whole segment assert sol.maxPotholes("xxxxx", 4) == 3 # partial repair

assert sol.maxPotholes("x.x.x", 6) == 3 # three isolated potholes assert sol.maxPotholes("x.x.x", 5) == 2 # insufficient for all

assert sol.maxPotholes("xxx.xxx", 8) == 6 # repair both segments assert sol.maxPotholes("xxx.xxx", 5) == 3 # repair one segment

assert sol.maxPotholes("xxxxxxxxxx", 11) == 10 # large segment exact budget assert sol.maxPotholes("xxxxxxxxxx", 2) == 1 # smallest valid repair

assert sol.maxPotholes(".", 100) == 0 # single smooth cell assert sol.maxPotholes("x" * 100000, 100001) == 100000 # maximum constraints

provided examples

assert Solution().maxPotholes("..", 5) == 0 # no potholes assert Solution().maxPotholes("..xxxxx", 4) == 3 # partial segment taken assert Solution().maxPotholes("x.x.xxx...x", 14) == 6 # multiple segments

edge cases

assert Solution().maxPotholes("x", 1) == 1 # single pothole minimal budget assert Solution().maxPotholes("x", 0) == 0 # cannot afford overhead assert Solution().maxPotholes("xxxxx", 10) == 5 # single full segment assert Solution().maxPotholes("x.x.x.x.x", 20) == 5 # many isolated segments assert Solution().maxPotholes("." * 10, 5) == 0 # all smooth road

### Test Summary

| Test | Why |
| --- | --- |
| `"..", 5` | No potholes present |
| `"..xxxxx", 4` | Partial repair of large segment |
| `"x.x.xxx...x", 14` | Repair all potholes |
| `"x", 1` | Budget below minimum repair cost |
| `"x", 2` | Exact minimum repair |
| `"xxxxx", 6` | Full segment repair |
| `"xxxxx", 4` | Partial segment repair |
| `"x.x.x", 6` | Multiple isolated potholes |
| `"x.x.x", 5` | Budget cannot cover all isolated potholes |
| `"xxx.xxx", 8` | Multiple equal segments |
| `"xxx.xxx", 5` | Greedy choice among segments |
| `"xxxxxxxxxx", 11` | Exact full-repair budget |
| `"xxxxxxxxxx", 2` | Smallest nonzero repair |
| `"." ,100` | No potholes with large budget |
| Maximum constraint case | Performance validation |

## Edge Cases

### No Potholes Exist

A road such as `"...."` contains no potholes. The segment extraction phase produces an empty array. Since there are no segments to process, the algorithm immediately returns `0`. This avoids any special-case handling later in the logic.

### Budget Too Small to Start Any Repair

Repairing even one pothole costs `2`. If the budget is `1`, no repair operation can be performed. During processing, the condition `budget <= 1` causes the algorithm to stop immediately, correctly returning zero repaired potholes.

### One Large Segment With Insufficient Budget

Consider `"xxxxxxxxxx"` with budget `5`. The segment length is `10`, but repairing all ten potholes would cost `11`. Instead, the algorithm computes the largest affordable repair length as `budget - 1 = 4`. Repairing four potholes costs exactly `5`, which fully utilizes the available budget and yields the maximum possible answer.

### Many Isolated Potholes

For a road like `"x.x.x.x.x"`, every pothole forms its own segment. Each repair costs `2` because each segment has length `1`. The algorithm naturally accounts for the repeated setup costs and repairs as many isolated potholes as the budget permits. This case is important because isolated potholes are much less cost efficient than long contiguous segments.

### Budget Large Enough To Repair Everything

When the budget exceeds the total cost of repairing all segments, every segment is repaired completely. The algorithm processes all sorted segments and returns the total number of potholes in the road, which is clearly optimal.
| "..", 5 | no potholes |
| "..xxxxx", 4 | partial segment selection |
| "x.x.xxx...x", 14 | multiple segments |
| "x", 1 | minimal valid case |
| "x", 0 | budget too small for cost |
| "xxxxx", 10 | single full block |
| "x.x.x.x.x", 20 | many overhead penalties |
| all dots | no repair needed |

## Edge Cases

One important edge case is when the road contains no `'x'` at all. In this case, the algorithm correctly produces an empty segment list and returns zero immediately, since no repairs are possible regardless of budget.

Another edge case is a single long contiguous block of `'x'`. This is the most efficient scenario because the overhead cost of `+1` is amortized over a large number of potholes. The greedy strategy naturally prioritizes this, ensuring it is taken if budget allows.

A third edge case is when potholes are fully isolated, such as `"x.x.x.x"`. Here, every pothole incurs its own overhead cost, making total cost significantly higher. The algorithm handles this correctly by treating each as a separate segment and ensuring budget feasibility before selection.