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).

Description Hints 3 Solution Video 12:11

3119. Maximum Number of Potholes That Can Be Fixed

Medium53.3% acceptance2 companiesPremium elsewhere, free here

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

Asked at 2 companies

Geico Microsoft

Topics

Hints open one at a time

Hint 1

Find all consecutive blocks of ’x’.

Hint 2

Sort them by their length.

Hint 3

Try to fix the block from the largest one until you have enough budget.

12:11

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

".."
5

Input

"..xxxxx"
4

Input

"x.x.xxx...x"
14

Your code is saved on this device.Solution