Longest Run of Healthy Log Entries After One Exactly-k Maintenance Window
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A service records its health in a log string, one character per time step: `1` means the service was running normally at that step and `0` means it had failed. You may perform at most one maintenance operation. The operation selects one contiguous block of exactly `k` consecutive positions of the log and changes every `0` inside the block to `1`; positions that are already `1` stay `1`. Choose the block, or skip the operation, so that the longest run of consecutive `1`s in the resulting log is as long as possible, and return that length.
The block always covers exactly `k` adjacent positions. This is not the same as changing any `k` zeros of your choice: two zeros that are far apart cannot both be repaired by a single operation.
### Function Signature
```python
def longest_uptime_after_maintenance(log: str, k: int) -> int:
```
### Rules
- `log[i]` is the status at time step `i` (0-indexed).
- If the operation is performed, it chooses a start index `s` with `0 <= s <= len(log) - k` and sets positions `s` through `s + k - 1` to `1`.
- The result is the length of the longest block of consecutive `1`s in the log after the optional operation, returned as a single integer.
### Constraints
- `1 <= len(log) <= 10^5`
- `1 <= k <= len(log)`
- Every character of `log` is `'0'` or `'1'`.
### Examples
**Example 1**
```text
Input: log = "1001110", k = 2
Output: 6
```
Repairing positions 1 and 2 gives `"1111110"`, whose first six steps are all `1`.
**Example 2**
```text
Input: log = "1010101", k = 2
Output: 3
```
Any block of length 2 covers two adjacent positions and so repairs only one of the zeros; for example, positions 1 and 2 give `"1110101"`. No choice of block produces a run longer than 3. Repairing the zeros at positions 1 and 3 together would give a run of 5, but they do not fit inside one block of length 2.
**Example 3**
```text
Input: log = "111", k = 2
Output: 3
```
The log is already all `1`, and any block leaves it unchanged.
Overview: An online-assessment coding problem on a binary service log where 1 means healthy and 0 means failed. You may repair one contiguous window of exactly k entries, turning its zeros into ones, and must return the longest possible run of consecutive ones. It tests linear scanning of runs and careful handling of the fixed window length.
Read the full Amazon Software Engineer interview experience this question came from
A service records its health in a log string `log`, one character per time step: `1` means the service was running normally at that step and `0` means it had failed. `log[i]` is the status at time step `i` (0-indexed).
You may perform **at most one** maintenance operation. The operation chooses a start index `s` with `0 <= s <= len(log) - k` and sets positions `s` through `s + k - 1` to `1`: every `0` inside the block becomes `1`, and positions that are already `1` stay `1`. The block always covers exactly `k` adjacent positions. This is not the same as changing any `k` zeros of your choice: two zeros that are far apart cannot both be repaired by a single operation.
Choose the block, or skip the operation, so that the longest run of consecutive `1`s in the resulting log is as long as possible, and return that length as a single integer.
Implement `longest_uptime_after_maintenance(log, k)`.
### Constraints
- `1 <= len(log) <= 10^5`
- `1 <= k <= len(log)`
- Every character of `log` is `'0'` or `'1'`.
The answer never exceeds `len(log) <= 10^5`, so it fits in a 32-bit signed integer (`int` in Java and C++).
### Examples
**Example 1**
```text
Input: log = "1001110", k = 2
Output: 6
```
Repairing positions 1 and 2 gives `"1111110"`, whose first six steps are all `1`.
**Example 2**
```text
Input: log = "1010101", k = 2
Output: 3
```
Any block of length 2 covers two adjacent positions and so repairs only one of the zeros; for example, positions 1 and 2 give `"1110101"`. No choice of block produces a run longer than 3. Repairing the zeros at positions 1 and 3 together would give a run of 5, but they do not fit inside one block of length 2.
Constraints
- 1 <= len(log) <= 10^5
- 1 <= k <= len(log)
- Every character of log is '0' or '1'.
Examples
Input: ('1001110', 2)
Expected Output: 6
Explanation: Source Example 1: the block at positions 1-2 joins the 1 at index 0 with the run at 3..5, giving 6.
Input: ('1010101', 2)
Expected Output: 3
Explanation: Source Example 2: every length-2 block repairs only one zero; the 'any k zeros' answer 5 is wrong.
Hints
- The operation only turns 0s into 1s, so it never shortens a run; focus on the run that ends up containing the block.
- After the block is placed, the run containing it is the block itself plus the 1s that touch it immediately on its left and on its right.
- There are only len(log) - k + 1 legal start positions; find a way to know the 1s bordering each block without rescanning the log every time.