Maximum Number of Potholes That Can Be Fixed

Maximum Number of Potholes That Can Be Fixed - 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.

Input & Output

Example 1 — Basic Road Repair

$ Input: road = ".xx.xxx.x", budget = 7

› Output: 5

💡 Note: We have segments [2,3,1] with costs [3,4,2]. Best strategy: select segments of length 3 (cost 4) and length 2 (cost 3), total cost = 7, total potholes = 5

Example 2 — Limited Budget

$ Input: road = "...x.xx.xxx..", budget = 5

› Output: 3

💡 Note: Segments [1,2,3] with costs [2,3,4]. We can afford segment of length 3 (cost 4) for maximum potholes, or segments [1,2] (cost 5). Both give 3 potholes

Example 3 — No Budget

$ Input: road = "xx.xx", budget = 1

› Output: 0

💡 Note: Segments [2,2] both cost 3 each, but budget is only 1. Cannot afford any repairs

Constraints

1 ≤ road.length ≤ 10⁵
1 ≤ budget ≤ 10⁶
road consists only of characters '.' and 'x'

Visualization

Tap to expand

Understanding the Visualization

Input

Road with potholes 'x' and budget constraint

Find Segments

Group consecutive potholes into repair segments

Optimal Selection

Choose most efficient segments within budget

Key Takeaway

🎯 Key Insight: Greedy selection by efficiency (potholes per dollar) gives optimal solution

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that longer consecutive segments are more cost-efficient to repair. The optimal approach uses a greedy algorithm that sorts segments by efficiency (potholes per dollar) and selects the most efficient ones first. Time: O(n + k log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^k × k)	O(k)	Generate all possible combinations of pothole segments and find the maximum within budget
Greedy Approach - Sort by Efficiency	O(n + k log k)	O(k)	Sort segments by efficiency (potholes per dollar) and greedily select the most efficient ones

Brute Force - Try All Combinations — Algorithm Steps

Find all consecutive pothole segments
Generate all possible combinations of segments
For each combination, check if total cost ≤ budget
Return maximum potholes from valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Segments

Identify consecutive pothole groups

Generate Combinations

Try all possible segment selections

Check Budget

Find maximum potholes within budget

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* road, int budget) {
    // Find all consecutive pothole segments
    int segments[1000];
    int segCount = 0;
    int i = 0;
    int len = strlen(road);
    
    while (i < len) {
        if (road[i] == 'x') {
            int length = 0;
            while (i < len && road[i] == 'x') {
                length++;
                i++;
            }
            segments[segCount++] = length;
        } else {
            i++;
        }
    }
    
    int maxPotholes = 0;
    
    // Try all possible combinations of segments
    for (int mask = 0; mask < (1 << segCount); mask++) {
        int totalCost = 0;
        int totalPotholes = 0;
        
        for (int j = 0; j < segCount; j++) {
            if (mask & (1 << j)) {
                int segmentLength = segments[j];
                int cost = segmentLength + 1;
                totalCost += cost;
                totalPotholes += segmentLength;
            }
        }
        
        if (totalCost <= budget) {
            if (totalPotholes > maxPotholes) {
                maxPotholes = totalPotholes;
            }
        }
    }
    
    return maxPotholes;
}

int main() {
    char road[10001];
    int budget;
    
    fgets(road, sizeof(road), stdin);
    road[strcspn(road, "\n")] = 0;
    
    scanf("%d", &budget);
    
    int result = solution(road, budget);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^k × k)

2^k combinations where k is number of segments, k time to check each

✓ Linear Growth

Space Complexity

O(k)

Store list of segments

✓ Linear Space

24.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler