Glaze run

Tiles leave the kiln in whatever order the trays were loaded, and a crate only sells if every tile carries the same glaze. The retouch booth fixes a few of them; how long a crate does that buy?

The problem

Each tile comes off the belt stamped with a one-letter glaze code — S for sand, K for kelp, D for dune. A crate takes one unbroken stretch of belt, and passes inspection only when every tile in it shares a code.

Before crating, the booth may re-glaze at most retouches tiles, each to any code you choose. Re-glazing never moves a tile or lets you skip one: the crate stays contiguous. Report the longest stretch that can be made single-glaze inside the budget.

Input. belt — a string of uppercase letters, one glaze code per tile in belt order. retouches — an integer, how many tiles the booth may re-glaze.

Output. The length of the longest single-glaze stretch achievable.

Example.

belt = "CCDDDCED", retouches = 2   ->  6

Tiles 2 through 7 read DDDCED. Re-glaze the C and the E to dune: six tiles match. Every stretch of seven costs at least three retouches.

A second example, which breaks the guess that the answer sits on the belt's most common glaze:

belt = "SSSKKKKSS", retouches = 1   ->  5

Sand appears five times and kelp four, yet the winning crate is kelp: SKKKK at tiles 2 through 6 costs one retouch. The best sand stretch one retouch rescues is SSSK, four tiles.

Constraints.

• 0 <= len(belt) <= 10^5
• every character of belt is an uppercase letter A–Z
• 0 <= retouches <= len(belt)
• an empty belt reports 0

Hints

Approach

Brute force

Try every pair of endpoints and count glazes inside each: n(n+1)/2 stretches, about 5 × 10⁹ for 10⁵ tiles. Counting incrementally as the right end slides still leaves O(n²) tile reads.

The insight

A stretch costs length - (count of its most common glaze), and that cost never falls when the right end moves further, so the left end never has to move backwards.

Extending adds one tile: the length rises by one and the best count by at most one, so cost is non-decreasing to the right. That is the precondition a forward window needs. Once tiles 4 through 30 prove unaffordable, so are tiles 4 through 31: index 4 is dead for good, and every tile enters and leaves once.

Algorithm

1. Start with an empty counter, left = 0, best = 0.
2. For each right, add belt[right] to the counter.
3. While (right - left + 1) - max(counter) exceeds retouches, decrement counter[belt[left]] and advance left.
4. Record best = max(best, right - left + 1).
5. Return best.

Complexity

Time O(n · A) with A the 26 glaze codes — each tile is added and removed once, each step scans the counter for its maximum. Space O(A): at most 26 entries, whatever the belt length.

Solution

"""Glaze run — a forward-only sliding window over glaze counts."""


def retouch_cost(window_length, counts):
    """Tiles inside the window that do not carry its most common glaze."""
    return window_length - max(counts.values())


def solve(belt, retouches):
    counts = {}
    left = 0
    best = 0
    for right, glaze in enumerate(belt):
        counts[glaze] = counts.get(glaze, 0) + 1
        # invariant after this loop: belt[left..right] costs at most `retouches`,
        # and no stretch starting before `left` can ever be affordable again.
        while retouch_cost(right - left + 1, counts) > retouches:
            counts[belt[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

TESTS = [
    (("CCDDDCED", 2), 6),
    (("SSSKKKKSS", 1), 5),
    (("SSK", 0), 2),
    (("", 3), 0),
    (("WWWW", 0), 4),
    (("SKSK", 4), 4),
    (("K", 0), 1),
]

Pitfalls

• Picking the target glaze before you slide. Sweeping once for the belt's most common code returns 4 on "SSSKKKKSS" with one retouch, not 5. The target is whatever dominates the current window, and it changes.
• Shrinking with if instead of while. Dropping a tile of the dominant glaze lowers the length and the maximum together, leaving the cost unchanged. "SSK" on budget 0 needs two shrink steps; one if leaves you measuring a crate you cannot pay for.
• Forgetting to decrement when left advances. The counter then describes the whole prefix, its maximum is too large, the budget never trips, and the answer is always len(belt).

Variants

• Two pointers — the converging form of the same two-index idea, where the ends walk toward each other on sorted data rather than both forward.
• A related exercise caps the distinct glazes in a crate instead of the retouches: same counter, different admission test.