3119. Maximum Number of Potholes That Can Be Fixed - Detailed Explanation

Problem Statement

Description:
You are given a binary string road of length n where:

• '1' represents a pothole that needs to be fixed.
• '0' represents a smooth section of the road.

You are also given an integer k (with 1 ≤ k ≤ n) representing the length of a contiguous segment on which a repair team can operate. When deployed on a segment, the team fixes every pothole (i.e. every '1') within that segment.

Your task is to choose a segment of length k such that the number of potholes fixed is maximized. Return that maximum number.

Example 1:

• Input:
  road = "101110"
  k = 3

• Explanation:
  Consider all contiguous segments of length 3:

  • Segment "101" (indices 0–2) → potholes = 1 + 0 + 1 = 2
  • Segment "011" (indices 1–3) → potholes = 0 + 1 + 1 = 2
  • Segment "111" (indices 2–4) → potholes = 1 + 1 + 1 = 3
  • Segment "110" (indices 3–5) → potholes = 1 + 1 + 0 = 2

  The maximum number fixed is 3.

• Output:
  3

Example 2:

• Input:
  road = "00000"
  k = 2

• Explanation:
  Every segment contains only smooth road (0’s), so no potholes are fixed.

• Output:
  0

Example 3:

• Input:
  road = "11111"
  k = 3

• Explanation:
  Every segment of length 3 consists entirely of potholes. Hence, the maximum fixed is 3.

Constraints:

• 1 ≤ road.length ≤ 10⁵
• road[i] is either '0' or '1'.
• 1 ≤ k ≤ road.length

Hints

• Hint 1:
  A brute-force solution would examine every contiguous segment of length k and count the potholes. However, with up to 10⁵ characters, this approach is too slow if you recount every segment from scratch.

• Hint 2:
  Think about how you can use a sliding window to maintain a running count of potholes. As you move the window one step to the right, update the count by subtracting the leftmost value and adding the new rightmost value.

• Hint 3:
  Alternatively, you can precompute a prefix sum array for the number of potholes up to each index. Then the pothole count for any segment can be computed in constant time.

Approaches

Approach A: Brute Force (Not Recommended)

Idea:

• For every starting index i (from 0 to n – k), count the number of '1' characters in the substring road[i:i+k].
• Update the maximum count found.

Downsides:

• Counting each segment separately leads to O(n * k) time, which is inefficient when n is large.

Approach B: Sliding Window (Optimal)

Idea:

• Initialize a window of size k and count the number of potholes in it.
• Slide the window one index at a time. For each move, subtract the count contributed by the element that is leaving the window and add the count for the new element entering the window.
• Track the maximum pothole count seen during these updates.

Benefits:

• Each character is processed only twice (once when entering and once when leaving the window), yielding an overall time complexity of O(n).

Pseudo-code:

count = number of '1's in road[0:k]
maxCount = count
for i from k to n-1:
    if road[i] is '1': count++ 
    if road[i - k] is '1': count--
    maxCount = max(maxCount, count)
return maxCount

Approach C: Prefix Sum (Alternative)

Idea:

• Create a prefix sum array where prefix[i] represents the number of potholes from index 0 to i-1.
• The count in any segment road[i:i+k] is given by prefix[i+k] - prefix[i].
• Iterate over all possible starting positions to compute the maximum count.

Benefits:

• Allows constant-time query for any segment after O(n) preprocessing.
• Overall time complexity is O(n).

Step-by-Step Walkthrough (Sliding Window Approach)

Let’s illustrate the sliding window method with Example 1: road = "101110", k = 3.

1. Initialization:

   • Consider the first window covering indices 0 to 2: "101".
   • Count = 1 (for index 0) + 0 (for index 1) + 1 (for index 2) = 2.
   • Set maxCount = 2.

2. First Slide (indices 1 to 3):

   • Remove road[0] which is '1' → count becomes 2 – 1 = 1.
   • Add road[3] which is '1' → count becomes 1 + 1 = 2.
   • maxCount remains 2.

3. Second Slide (indices 2 to 4):

   • Remove road[1] which is '0' → count remains 2.
   • Add road[4] which is '1' → count becomes 2 + 1 = 3.
   • Update maxCount = max(2, 3) = 3.

4. Third Slide (indices 3 to 5):

   • Remove road[2] which is '1' → count becomes 3 – 1 = 2.
   • Add road[5] which is '0' → count remains 2.
   • maxCount remains 3.

5. Final Answer:
   The maximum number of potholes that can be fixed is 3.

Code Implementations

Python Implementation