Maximum Number of Potholes That Can Be Fixed - Solution & Explanation

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.