Skip to content

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

DifficultyMedium

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

Thinking

A run of \(k\) potholes costs \(k+1\) to fix and the budget is limited. Choosing a repair length for every run independently explodes with the number of runs.

Longer runs yield more fixed holes per unit leftover. After fixing as many length-\(k\) runs as the budget allows, unused runs become length \(k-1\) runs.

Count runs by length, then from large \(k\) downward take \(t=\min(\textit{budget}/(k+1),cnt[k])\), add \(t\cdot k\) to the answer, and fold the rest into \(cnt[k-1]\) until the budget is gone.

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

 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 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 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
class 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;
    }
}

 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
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

 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
31
32
33
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
}

Comments