Longest ON run with k range flips

Reframe the operation. A flip of a contiguous range that covers both ON and OFF servers turns the ON ones OFF, so a flip only helps the final run when it lands exactly on a block of OFF servers. Say the run we want ends up being the window s[l..r]. Every OFF server inside the window has to be flipped an odd number of times, and every ON server inside it an even number of times. Take the XOR of all the ranges we flip. Its restriction to the window must be exactly the set of OFF positions there. If the window holds z maximal OFF blocks, that set is z separate intervals, and the XOR of k intervals has at most 2k boundary points, which is at most k intervals. So:

A window can be made all ON with at most k flips if and only if it contains at most k maximal blocks of 0s.

The bound is also reachable: flip each OFF block on its own. The problem is now "find the longest substring that contains at most k zero-blocks". This looks like LeetCode 1004 (flip at most k zeros), but here we count blocks, not zeros.

Brute force. For every start l, extend r and count zero-blocks, adding one each time s[r] == '0' and s[r-1] != '0' (or r == l). Stop once the count passes k. This is O(n²) time and enough to state first.

Optimal: sliding window. Move r from left to right and keep blocks, the number of zero-blocks that start inside [l, r]:

• When s[r] == '0' and the previous character in the window is not 0 (or the window is empty), a new block starts, so blocks += 1.
• While blocks > k, advance l. Leaving position l removes a block only when s[l] == '0' and s[l+1] != '0', that is, when we pop the last zero of the leftmost block. A block cut at its left edge still counts until its last zero leaves.
• Record r - l + 1.

Invariant: blocks equals the number of maximal zero-blocks of the substring s[l..r], and it is <= k after the shrink loop. Both pointers only move forward, so the scan is O(n). The k == 0 case drops out naturally: the answer is the longest run of 1s already present.

An equivalent compact view: run-length encode s into groups. The best window starts and ends on group boundaries and spans at most k zero-groups plus the one-groups between and around them. A window over the groups gives the same answer in O(number of groups).

from typing import List, Tuple


def max_consecutive_on(server_states: str, k: int) -> int:
    """Longest run of '1's reachable with at most k contiguous-range flips."""
    s = server_states
    n = len(s)
    best = 0
    left = 0
    blocks = 0  # maximal '0' blocks inside s[left..right]
    for right in range(n):
        if s[right] == "0" and (right == left or s[right - 1] != "0"):
            blocks += 1
        while blocks > k:
            # Popping the last zero of the leftmost block removes that block.
            if s[left] == "0" and (left + 1 > right or s[left + 1] != "0"):
                blocks -= 1
            left += 1
        best = max(best, right - left + 1)
    return best


def best_flip_plan(server_states: str, k: int) -> Tuple[int, List[Tuple[int, int]]]:
    """Same answer, plus the inclusive ranges to flip (follow-up: show the plan)."""
    s = server_states
    groups: List[Tuple[str, int, int]] = []  # (char, start, end)
    i = 0
    while i < len(s):
        j = i
        while j + 1 < len(s) and s[j + 1] == s[i]:
            j += 1
        groups.append((s[i], i, j))
        i = j + 1

    best, plan = 0, []
    lo = 0
    zeros = 0
    for hi, (ch, _, _) in enumerate(groups):
        if ch == "0":
            zeros += 1
        while zeros > k:
            if groups[lo][0] == "0":
                zeros -= 1
            lo += 1
        if lo <= hi:
            length = groups[hi][2] - groups[lo][1] + 1
            if length > best:
                best = length
                plan = [(a, b) for c, a, b in groups[lo:hi + 1] if c == "0"]
    return best, plan


if __name__ == "__main__":
    assert max_consecutive_on("1001011", 1) == 4
    assert max_consecutive_on("1001011", 2) == 7
    assert max_consecutive_on("0000", 1) == 4
    assert max_consecutive_on("0000", 0) == 0
    assert max_consecutive_on("1111", 0) == 4
    assert max_consecutive_on("0101010", 2) == 5
    assert max_consecutive_on("", 3) == 0
    assert best_flip_plan("1001011", 1) == (4, [(1, 2)])
    assert best_flip_plan("0101010", 2)[0] == 5
    print("ok")

• max_consecutive_on: O(n) time, because each pointer moves at most n times. O(1) extra space.
• best_flip_plan: O(n) time to run-length encode and slide over the groups. O(g) space for the g groups, plus the returned plan, which has at most k ranges.

• "1001011", k=1 → 4: flip [1,2] to get 1111011, or [4,4] to get 1001111.
• "1001011", k=2 → 7: flip [1,2] and [4,4].
• "0101010", k=2 → 5: for example, flip the zeros at 2 and 4 to cover indices 1–5.
• "0000", k=1 → 4: one flip covers the whole block.
• "0000", k=0 → 0: no flips, no ON servers.
• "1111", k=0 → 4: already all ON.
• "10", k=5 → 2: a large k is capped by the length.
• "", k=3 → 0: empty cluster.
• "0110", k=1 → 3: you can include only one of the two edge zeros.
• Random cross-check: compare with an exhaustive search over all sets of up to k ranges for n <= 8.

1. Return the actual flips. Slide over the run-length groups (best_flip_plan) and output the zero-groups inside the best window. With ties, prefer the leftmost window, or the one that uses the fewest flips.
2. Minimum flips to reach a target run length L. Binary search on k with the O(n) check gives O(n log n). Better: slide a window of exactly L over the string, count its zero-blocks with prefix sums of "a block starts here" plus a fix-up at the window's left edge, and take the minimum. That is O(n).
3. Answer many k values. The answer is non-decreasing in k. For q queries, run the O(g) group window per query, giving O(q·g). Alternatively, for each j, compute the best window covering exactly j consecutive zero-groups (a window over j consecutive zero-groups extends into the one-groups on either side). Take prefix maxima over j to get best[k] for every k. That is O(g²), or O(g) per j.
4. Circular rack (server n-1 is next to server 0). Double the string and cap the window length at n. If the whole ring would be covered, treat it as a full loop: a ring with z zero-blocks needs z flips, and the answer is n if z <= k.
5. Live updates (servers toggle while queries arrive). Keep a segment tree over the groups, or over positions. For a fixed small k, each node stores, for each j <= k, the best inner, prefix and suffix runs that use j blocks. Merging is O(k²), so each update or query costs O(k² log n).

Mid-level (L4)

• Sees that a flip covering ON servers hurts, so each flip should cover exactly one OFF block.
• Reduces the problem to "longest window with at most k zero-blocks" and codes a correct sliding window. O(n²) with clear reasoning is acceptable as a first pass.
• Handles k = 0, an all-ON string, an all-OFF string and the empty string.

Senior (L5)

• Justifies why combined or overlapping flips can't do better: the XOR of k intervals has at most 2k boundaries.
• Gets O(n) with clean block bookkeeping (counting a block in on its first zero and out on its last zero), and explains the invariant.
• Returns the flip plan, and handles the minimum-flips-for-length-L variant without starting over.

Staff (L6+)

• Generalizes cleanly to all-k queries, the circular case and streaming updates, and states the complexity trade-offs, including the segment-tree merge.
• Brings up testing strategy: a brute-force oracle over small n with random strings.
• Connects the model to the real operation: real ranges carry costs or length limits. Explains how a per-flip cost or a maximum range length changes the reduction. A maximum length splits long OFF blocks into several flips, so each block costs ceil(len/L), and a window keyed on that cost works.