Cones on the loom

The shuttle race holds a few cones and no more. Swapping one stops the loom, so the question is how far the card runs between stops.

The problem

A hand loom weaves one pick at a time — one pass of the shuttle, one row of weft. The pattern card lists the colour of every pick in order. The shuttle race holds at most cones cones, and loading a different colour means stopping to rethread.

Find the longest unbroken stretch of the card weavable without a stop: the longest run of consecutive picks using at most cones distinct colours. A stretch may repeat a colour freely, since a cone already in the race costs nothing to reuse.

Input. picks — a list of colour names, one per pick, in card order. cones — how many cones the shuttle race holds.

Output. The length of the longest consecutive stretch using at most cones distinct colours.

Example.

picks = ["indigo", "madder", "indigo", "weld", "indigo", "madder"], cones = 2   ->  3

The stretch indigo, madder, indigo uses two colours over three picks. Adding the weld makes three, over budget.

A second example, showing a repeated colour costs nothing and an empty budget buys nothing:

picks = ["ochre", "ochre", "ochre", "cochineal"], cones = 1   ->  3
picks = ["ochre"],                                cones = 0   ->  0

Three picks of ochre need one cone however often it repeats. With no cones the answer is 0, not 1.

Constraints.

• 0 <= len(picks) <= 10^5
• 0 <= cones <= 100
• Each colour name is 1 to 20 lowercase letters.

Hints

Approach

Brute force

For every starting pick, extend rightward growing a set of colours until it exceeds the budget: roughly n²/2 steps, 5 billion on a card of 10⁵ picks.

The insight

A stretch that fits the cone budget still fits it when you cut picks off the front, so once the right edge forces a stop the left edge only has to move forward, never back.

Removing a pick can never add a colour, so legality is closed under trimming from the left. Each right edge therefore has one earliest legal start, and those starts rise as the right edge advances, so a single forward sweep of each edge covers every candidate.

One bookkeeping detail keeps each move constant time: hold a count per colour. Trimming decrements a count, and only a count that hits zero removes a colour, so the key count is exactly the cones in use.

Algorithm

1. Keep counts, a map from colour to its pick count in the stretch, plus start = 0 and best = 0.
2. For each index end, increment counts[picks[end]].
3. While the map holds more than cones keys: decrement picks[start]'s count, delete the key if it reached zero, and advance start.
4. Update best with end - start + 1, then return it at the end.

Complexity

Time O(n) — each pick is added once and removed at most once: at most 2n map operations. Space O(cones), since the loop trims the moment the map exceeds cones + 1 colours.

Solution

"""Cones on the loom — longest window with at most k distinct colours."""


def solve(picks, cones):
    counts = {}
    start = 0
    best = 0
    for end, colour in enumerate(picks):
        counts[colour] = counts.get(colour, 0) + 1
        # Invariant: counts holds one key per colour present in picks[start..end]
        # with its multiplicity, so len(counts) is exactly the cones in use.
        # A colour leaves the race only when its last pick is trimmed away.
        while len(counts) > cones:
            leaving = picks[start]
            counts[leaving] -= 1
            if counts[leaving] == 0:
                del counts[leaving]
            start += 1
        if end - start + 1 > best:
            best = end - start + 1
    return best

TESTS = [
    ((["indigo", "madder", "indigo", "weld", "indigo", "madder"], 2), 3),
    ((["ochre", "ochre", "ochre", "cochineal"], 1), 3),
    ((["ochre"], 0), 0),
    (([], 3), 0),
    ((["flax", "woad", "flax", "woad", "flax"], 2), 5),
    ((["indigo", "madder", "indigo", "weld", "indigo", "madder"], 3), 6),
    ((["saffron", "woad", "logwood"], 5), 3),
]

Pitfalls

• Tracking colours in a set instead of counts. Removing picks[start] from a set drops a colour still in use later on. With two cones and ["indigo", "madder", "indigo", "weld"] the set loses indigo when the start passes index 0, so madder, indigo, weld scores as legal on two colours when it uses three.
• Trimming with if instead of while. Dropping the front pick may take a count from 2 to 1 and free no cone: the pick at index 3 of the first example needs two trims.
• Forgetting cones = 0. The trim loop must be able to empty the window, leaving start one past end and a length of 0. Code that assumes the window always holds a pick reports 1, and code that measures before trimming reports an over-budget stretch.

Variants

• No repeats on air — the same window with the budget fixed at "every value distinct", which a last-seen index handles without counts.
• Shortest soak — the same edges, trimmed toward a shortest answer rather than a longest one.