Maximum Number of Potholes That Can Be Fixed solution and explanation
The 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.
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 <= 1051 <= budget <= 105 + 1roadconsists only of characters'.'and'x'.
Approach overview
Problem Overview: You receive a road represented as a string where potholes appear as consecutive segments. Repairing a segment has a fixed setup overhead plus a cost proportional to the number of potholes fixed. Given a repair budget B, the task is to maximize how many potholes you can repair.
Approach 1: Brute Force Segment Selection (Exponential)
Start by scanning the string and extracting every contiguous pothole segment. Then try all combinations of segments to see which set fits within the budget and produces the highest number of repaired potholes. Each segment repair costs length + 1 due to the setup overhead. This approach quickly becomes infeasible because the number of segment combinations grows exponentially. Time complexity is O(2^k) where k is the number of pothole segments, and space complexity is O(k) for storing segment lengths.
Approach 2: Greedy with Sorting (O(n log n))
First iterate through the string and collect the length of every contiguous pothole segment. Each segment of length k costs k + 1 to repair. The key observation: because every segment has the same extra overhead of +1, repairing smaller segments first gives more potholes per unit budget. Store segment lengths in an array, sort them, and process from smallest to largest. If the remaining budget can cover the full cost k + 1, repair the entire segment and subtract the cost. If not, use the remaining budget to repair as many potholes as possible within that segment (up to budget - 1 because of setup cost). Time complexity is O(n log n) due to sorting, and space complexity is O(n) for storing segment lengths. This approach uses ideas from greedy algorithms and simple sorting.
Approach 3: Counting + Greedy Optimization (O(n))
Sorting can be avoided by counting segment lengths while scanning the road. Instead of storing every segment and sorting later, track them in frequency buckets keyed by length. Then iterate from the smallest length upward and greedily spend the budget repairing segments. This preserves the same greedy insight but reduces sorting overhead. The scan to detect segments takes O(n) time, and processing bucket counts also takes linear time relative to possible segment lengths. Space complexity remains O(n). This solution combines string traversal with a greedy cost allocation strategy.
Recommended for interviews: The greedy segment strategy with sorting is the expected answer. It shows you can convert a string parsing problem into a cost optimization problem and apply a greedy ordering. Mentioning the brute force approach demonstrates problem exploration, but the sorted greedy solution shows the optimization interviewers look for.
Solution
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(budget / (k + 1), 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:
def maxPotholes(self, road: str, budget: int) -> int:
road += "."
n = len(road)
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 ansclass Solution {
public int maxPotholes(String road, int budget) {
road += ".";
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) {
road.push_back('.');
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;
}
};function maxPotholes(road: string, budget: number): number {
road += '.';
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) {
road += '.';
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;
}
}func maxPotholes(road string, budget int) (ans int) {
road += "."
n := len(road)
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
}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
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Segment Selection | O(2^k) | O(k) | Conceptual baseline for small inputs or reasoning about segment choices |
| Greedy with Sorting | O(n log n) | O(n) | General solution; simple to implement and commonly expected in interviews |
| Counting + Greedy | O(n) | O(n) | When segment lengths are processed during scanning and sorting can be avoided |
Frequently asked questions
Is Maximum Number of Potholes That Can Be Fixed easy or hard?
The problem is rated Medium. The main difficulty is recognizing that each segment has a fixed overhead cost, which makes repairing smaller segments first the optimal greedy choice. Once that insight is clear, the implementation is straightforward.
Maximum Number of Potholes That Can Be Fixed Python/Java solution
Implementations typically scan the string, push segment lengths into a list, sort them, and greedily subtract costs from the budget while counting repaired potholes. The same logic translates directly across Python, Java, C++, Go, TypeScript, Rust, and C# since it relies on basic loops, arrays, and sorting utilities.
How to solve Maximum Number of Potholes That Can Be Fixed in O(n)?
Scan the road string once and record lengths of contiguous pothole segments. Instead of sorting them, maintain counts of segment lengths or process them in increasing order during traversal. Then greedily spend the repair budget starting from the smallest segments. This removes the sorting step and achieves O(n) time with O(n) space.
What is the best approach for Maximum Number of Potholes That Can Be Fixed?
The best approach uses a greedy strategy. First scan the string to extract lengths of consecutive pothole segments. Because repairing each segment has a fixed overhead cost, repairing smaller segments first maximizes the number of potholes fixed within the budget. Sorting the segment lengths and processing them greedily gives an O(n log n) solution.
Is Maximum Number of Potholes That Can Be Fixed asked at Google/Amazon/Meta?
Greedy budgeting problems over arrays or strings appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this problem test whether candidates can identify segments, model costs, and apply a greedy ordering to maximize output under constraints.
What data structure is used in Maximum Number of Potholes That Can Be Fixed?
The solution primarily uses arrays or lists to store lengths of pothole segments extracted from the string. Sorting or frequency counting is then applied to process segments in increasing order. The algorithm combines string traversal with greedy selection.
What is the time complexity of Maximum Number of Potholes That Can Be Fixed?
The typical optimal implementation runs in O(n log n) time due to sorting the pothole segment lengths. The initial scan of the string takes O(n). Space complexity is O(n) to store segment sizes. With counting-based optimization, the complexity can be reduced to O(n).