No repeats on air

A repeat inside one stretch breaks the station's rule. Where the next legal stretch starts is the whole question, and the tempting answer is wrong.

The problem

A community station runs an automated queue: a fixed list of tracks played in order, each tagged with the artist's short code. The programming rule says an artist may not appear twice inside one unbroken stretch of airtime — a station ident breaks the stretch and the count starts again.

The scheduler wants the longest stretch of consecutive tracks it can play before it is forced to drop an ident in: the longest run of consecutive tracks with no artist code repeated.

Input. queue — a list of artist codes, one per track, in play order.

Output. The length of the longest run of consecutive tracks containing no code twice.

Example.

queue = ["moss", "kestrel", "moss", "briar", "kestrel", "vole"]   ->  4

The run moss, briar, kestrel, vole has four distinct artists. Extending it left picks up the earlier kestrel, already in the run.

A second example, where a repeat outside the current stretch must be ignored:

queue = ["lark", "swift", "swift", "lark"]   ->  2
queue = ["heron", "heron", "heron"]          ->  1

The doubled swift restarts the stretch at index 2; the later lark was last heard at index 0, already behind that start, so it forces nothing. The answer is swift, lark. One artist on repeat gives stretches of one.

Constraints.

• 0 <= len(queue) <= 10^5
• Each code is 1 to 20 lowercase letters.
• The queue may be empty, in which case the answer is 0.

Hints

Approach

Brute force

Take every start, extend while the artists stay distinct, keep the longest. For 10⁵ tracks that is up to 5 billion membership checks, most re-verifying a prefix an earlier start already cleared.

The insight

When a repeat appears, the next legal stretch cannot begin earlier than one track past that artist's previous airing — so the left edge only ever moves forward.

A stretch stays legal when you trim tracks off its front — dropping a track can never create a repeat — so each right edge has a single earliest legal start, and that start is non-decreasing as the right edge advances. One forward sweep of each edge visits every candidate stretch.

The subtlety is that a previous airing may already sit behind the current start, in which case it is outside the stretch and irrelevant. Jumping the start to it would be moving backwards, which the argument forbids.

Algorithm

1. Keep last, a map from artist code to its most recent index, plus start = 0 and best = 0.
2. For each index i with code c:
3. If c is in last and last[c] >= start, set start = last[c] + 1.
4. Set last[c] = i.
5. Update best with i - start + 1.
6. Return best.

Complexity

Time O(n) — one pass, one average-constant map lookup and update per track. Space O(d) for d distinct artist codes; the map never grows past that.

Solution

"""No repeats on air — longest repeat-free stretch via two forward-only edges."""


def solve(queue):
    last_heard = {}
    start = 0
    best = 0
    for i, code in enumerate(queue):
        # Invariant: queue[start..i-1] has no repeated code. A previous airing
        # only breaks that if it is at or after start; an older one is outside
        # the stretch, and moving start back to it would undo settled work.
        if code in last_heard and last_heard[code] >= start:
            start = last_heard[code] + 1
        last_heard[code] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

TESTS = [
    ((["moss", "kestrel", "moss", "briar", "kestrel", "vole"],), 4),
    ((["lark", "swift", "swift", "lark"],), 2),
    ((["heron", "heron", "heron"],), 1),
    (([],), 0),
    ((["fox", "owl", "doe", "fox", "fox"],), 3),
    ((["fern", "gull", "fern", "gull", "wren"],), 3),
    ((["solo"],), 1),
]

Pitfalls

• Moving the start to last[c] + 1 without checking it is inside the stretch. On ["lark", "swift", "swift", "lark"] the final lark was last heard at index 0, and jumping there sets the start back to 1 — reporting 3 for a stretch that plays swift twice. Guard with last[c] >= start, or take a maximum.
• Clearing the map and restarting at every repeat. Correct and quadratic: a queue like a b c d a b c d … rebuilds the whole prefix every time.
• Returning the final stretch instead of the longest seen. On ["fox", "owl", "doe", "fox", "fox"] the queue ends on a stretch of one while the answer is three. Record the best on every step, seeded at 0 so an empty queue answers 0 instead of failing.

Variants

• Cones on the loom — the same window, with "no repeats" loosened to "at most k distinct", which needs counts rather than a last-seen index.
• Shortest soak — the same forward-only edges used to find the shortest qualifying window instead of the longest legal one.