Two cuts on the cone rod

The cones leave the winder in one long sequence, threaded onto a single steel rod. You get two cuts, and you want the piece between them as short as possible.

The problem

A dye house winds yarn onto cones and slides them, in winding order, onto one rod. Each cone carries a one-letter colour code: c crimson, o ochre, s slate, m moss, t teal. A weaver's order is written the same way — one letter per cone needed, so ctt means one crimson and two teal.

The rod cannot be picked apart: a cone lifted from the middle unspools everything behind it. So you cut the rod twice and keep the section between the cuts. That section must hold at least the ordered tally of every colour; extra cones inside it are waste, and allowed. Return the shortest such section, the one nearer the head of the rod on a tie, or the empty string if the rod cannot fill the order at all.

Input. reel — the colour codes in rod order. order — the tally the weaver needs; a repeated letter means that many cones.

Output. The shortest contiguous slice of reel whose tally covers order, leftmost on a tie, or '' if there is none.

Example.

reel = "cmmsotsscmot", order = "cot"   ->  "cmot"

The first crimson sits at the head, so the earliest section that works runs from index 0 to the teal at index 5 — six cones. Further along the three colours cluster, and indices 8 to 11 give four, one of them waste moss.

A second example, where counting distinct colours goes wrong:

reel = "ctcmt", order = "ctt"   ->  "tcmt"

The order needs two teal. The head ct carries both colour codes but only one teal, so the section has to stretch to the second teal at the tail.

Constraints.

• 1 <= len(reel) <= 10^5
• 1 <= len(order) <= 10^4
• Both strings are lowercase letters only.

Hints

Approach

Brute force

Try every pair of cut points and tally the section between them. That is n(n+1)/2 sections — about 5 · 10⁹ for a rod of 10⁵ cones, before a single letter is counted.

The insight

For each right cut there is only one left cut worth measuring — the furthest one along that still fills the order — and that left cut never moves backwards as the right cut advances.

Fix a left position l. Moving the right cut along only adds cones, so if reel[l..r] fills the order then reel[l..r+1] does too. The left positions that work for a given right end are therefore a prefix of the rod, whose last element is non-decreasing in r. That is the precondition a sliding window needs: both edges only move forward, so each cone is added once and dropped once.

Algorithm

1. Tally order into owed; set missing = len(order), what an empty section owes.
2. Advance the right edge one cone at a time. If owed[colour] > 0 the cone pays a debt, so decrement missing. Decrement owed[colour] either way, letting it go negative to record surplus.
3. While missing == 0, record the section's length if it beats the best, then advance the left edge: add 1 back to owed[reel[left]], and if that turns positive the section has lost a cone it needed, so missing += 1.
4. Return the recorded slice, or '' if nothing was recorded.

Complexity

Time O(n + m) — the right edge visits each of the n cones once, and the inner loop only moves the left edge forward, so it runs at most n times over the whole pass; the tally costs m. Space O(a), one counter per colour code — 26 at most, so constant.

Solution

"""Two cuts on the cone rod — shrinking sliding window over a colour tally."""

from collections import Counter


def solve(reel, order):
    if not order or len(order) > len(reel):
        return ""

    # owed[colour] > 0 means the window is still short of that colour.
    # It is allowed to go negative: a negative entry is surplus, and that
    # surplus is exactly what lets the left edge slide past a cone safely.
    owed = Counter(order)
    missing = len(order)               # cones the current window still owes

    best_start, best_len = 0, len(reel) + 1
    left = 0

    for right, colour in enumerate(reel):
        if owed[colour] > 0:           # this cone pays a debt rather than piling up
            missing -= 1
        owed[colour] -= 1

        while missing == 0:            # invariant: reel[left..right] covers the order
            if right - left + 1 < best_len:    # strict: ties keep the leftmost
                best_start, best_len = left, right - left + 1
            owed[reel[left]] += 1
            if owed[reel[left]] > 0:   # that cone was needed, so the window breaks
                missing += 1
            left += 1                  # left never moves back: each cone leaves once

    if best_len > len(reel):
        return ""
    return reel[best_start:best_start + best_len]

TESTS = [
    (("cmmsotsscmot", "cot"), "cmot"),     # page example 1
    (("ctcmt", "ctt"), "tcmt"),            # page example 2: multiplicity, not a set
    (("ossm", "oc"), ""),                  # a needed colour is absent
    (("cc", "ccc"), ""),                   # order longer than the rod
    (("c", "c"), "c"),                     # single cone
    (("ccc", "cc"), "cc"),                 # all equal; leftmost of the tied windows
    (("cco", "co"), "co"),                 # surplus must let the left edge advance
    (("tsc", "cst"), "tsc"),               # the whole rod is the answer
]

Pitfalls

• Testing distinct colours instead of counts. On reel = "ctcmt", order = "ctt", a set test accepts the two-cone head ct, which holds one teal where two were ordered. The real answer, tcmt, is twice as long.
• Clamping the tally at zero. If owed[colour] never drops below zero, then dropping a surplus cone from the left looks like breaking the order and the left edge stalls. On reel = "cco", order = "co" that returns cco instead of co.
• Measuring after the left edge moves. Record at the top of the shrink loop, while the section still fills the order. Moving first reports a length one too small, and a slice missing a cone.

Variants

• Two pointers — the lesson behind this window: why an edge that only moves forward may discard what it passes.
• A near relative, named without a link: pin the window to exactly len(order) cones and the shrink step disappears, leaving the question of whether any fixed-width section is an exact rearrangement of the order.