Two-ink run

A small press holds two ink cartridges at a time. Swapping one out stops the line, so the operator wants the longest run of queued jobs that needs no swap.

The problem

The queue is a string of ink codes, one character per job, in the order the jobs will print: c, m, y, k for the four inks the shop stocks. The press can hold any two of them, chosen freely before the run starts.

Find the length of the longest contiguous block of jobs that uses at most two distinct inks. Jobs cannot be reordered, and a block using only one ink is fine — the second cartridge simply sits idle.

Input. queue — a string of ink codes, possibly empty.

Output. An integer, the length of the longest block using at most two distinct inks.

Example.

queue = "ccmmyc"   ->  4

The block ccmm runs on cyan and magenta. Adding the y after it would need a third cartridge, and the tail myc needs three inks in three jobs.

A second example, where the best block is not at the front:

queue = "mccmmyyyym"   ->  7

The opening mccmm is five jobs on two inks, but mmyyyym starting at job 3 is seven on magenta and yellow. A method that grows a block from the start and stops at the first violation reports 5.

Constraints.

• 0 <= len(queue) <= 10^5
• Every character is one of c, m, y, k.

Hints

Approach

Brute force

Try every start, extend to every end, and track the distinct inks. That is n * (n + 1) / 2 blocks — 5 * 10^9 on a queue of 10^5 jobs — and most of the work re-derives what the previous start already established.

The insight

If a block starting at job i is illegal, so is every block starting at i that ends later, so the left edge only ever moves forward.

Adding a job can only raise the distinct count and removing one can only lower it, so the legality of a window is monotone in its left edge for a fixed right edge. That is the precondition the window needs: both pointers sweep the queue once, in the same direction, and the pair (left, right) is always the longest legal window ending at right.

Algorithm

1. Keep a map from ink code to how many jobs in the window use it.
2. Move right across the queue, incrementing the entry for that job's ink.
3. While the map holds three keys, decrement the count for the job at left, delete the key if the count reaches 0, and advance left.
4. Record right - left + 1 if it beats the best so far.
5. Return the best.

Complexity

Time O(n) — right advances n times and left never overtakes it, so the shrink loop runs at most n times in total. Space O(1): the map holds three keys at its largest.

Solution

"""Two-ink run — longest window holding at most two distinct ink codes."""


def solve(queue):
    loaded = {}                  # ink code -> how many jobs in the window use it
    left = 0
    longest = 0
    for right, ink in enumerate(queue):
        loaded[ink] = loaded.get(ink, 0) + 1
        while len(loaded) > 2:   # invariant: after this loop the window fits the press
            leaving = queue[left]
            loaded[leaving] -= 1
            if loaded[leaving] == 0:
                del loaded[leaving]
            left += 1
        longest = max(longest, right - left + 1)
    return longest

TESTS = [
    (("ccmmyc",), 4),
    (("mccmmyyyym",), 7),
    (("kkkk",), 4),
    (("cmyk",), 2),
    (("",), 0),
    (("c",), 1),
]

Pitfalls

• Shrinking with if instead of while. One removal is often not enough: from the window ccm, adding y needs three jobs dropped before a cartridge is freed, and a single if leaves the illegal window cmy.
• Leaving a zero count in the map. len(map) stays at 3 forever, left chases right to the end, and "mccmmyyyym" reports 1 instead of 7.
• Rebuilding a set over the window each step. It gives the right answer and restores the n * n running time the window was meant to remove.
• Returning left or the window contents. The answer is a length; on an empty queue it is 0, and no index exists to return.

Variants

• Exactly k stops — the same at-most-k window, generalised past two and counted rather than measured.