Maximum number of potholes that can be fixed

String Greedy Sorting

53.4% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_potholes(road: String, budget: i32) -> i32 {
    let bytes = road.as_bytes();
    let mut groups: Vec<i32> = Vec::new();
    let mut i = 0;
    while i < bytes.len() {
      if bytes[i] == b'x' {
        let mut j = i;
        while j < bytes.len() && bytes[j] == b'x' {
          j += 1;
        }
        groups.push((j - i) as i32);
        i = j;
      } else {
        i += 1;
      }
    }
    groups.sort_unstable_by(|a, b| b.cmp(a));
    let mut budget = budget;
    let mut total = 0;
    for g in groups {
      if budget <= 1 { break; }
      let fix = g.min(budget - 1);
      total += fix;
      budget -= fix + 1;
    }
    total
  }
}