Dye house shade index

A dye house filed its shade cards in an alphabet of its own and never wrote the alphabet down. The index survived, so the order can be read back out of it.

The problem

Every shade has a short lowercase code, and the cards are filed in the house's own alphabetical order — the same letters, a different sequence.

Filing works the way any dictionary order does: the first position where two codes differ decides, and the letter on the earlier card comes first. If one code is a prefix of the other, the shorter card is filed first.

Reconstruct an order over exactly the letters that appear. If the filing contradicts itself, report the empty string; if several orders explain it, report the one built by always taking the smallest available letter in ordinary a to z order.

Input. codes — a list of lowercase strings, in the order they are filed.

Output. A string containing each letter that appears, in the house's order, or "" when no order explains the filing.

Example.

codes = ["dc", "da", "cab", "cb", "ab", "b"]   ->  "dcab"

"dc" before "da" puts c before a; "da" before "cab" puts d before c; "cab" before "cb" puts a before b. Chained: d, c, a, b.

Example. A letter can appear without being constrained at all:

codes = ["mb", "ma"]   ->  "bam"

The only fact is b before a; m is unconstrained, and the tie-break takes the smallest ready letter at each step.

Example. A longer code filed ahead of its own prefix is impossible:

codes = ["glaze", "gla"]   ->  ""

Constraints.

• 1 <= len(codes) <= 2000
• 1 <= len(codes[i]) <= 20
• every code is lowercase Latin letters only
• the total length of all codes is at most 10^5

Hints

Approach

Brute force

Try every permutation of the letters present and check whether the index is sorted under it. With k distinct letters that is k! candidates: 3.6 million at k = 10, hopeless at k = 26.

The insight

Each pair of neighbouring cards contributes exactly one ordering fact, and any order consistent with all of them is a topological sort of the letters.

The comparison stops at the first difference, so that pair constrains nothing else, and the whole index collapses to at most n - 1 arrows over at most 26 letters. Topological sort needs those arrows acyclic, and acyclicity is exactly the statement "some order explains this filing" — a letter left over after peeling proves none does.

Algorithm

1. Collect every letter appearing in any code; those are the nodes.
2. For each adjacent pair, record one arrow at the first differing position.
3. If there is no difference and the longer card came first, return "".
4. Count incoming arrows; push every letter with none into a min-heap.
5. Pop the smallest ready letter, append it, decrement its successors, and push any that reach zero.
6. If fewer letters came out than went in, a cycle remains: return "".

Complexity

Time O(C + k log k) for total code length C and k distinct letters — one pass to build the arrows, then a peel over at most 26 nodes. Space O(k^2), which the 26-letter bound makes constant.

Solution

"""Dye house shade index — topological sort of the letter order the filing implies."""

import heapq
from collections import defaultdict


def implied_pairs(codes):
    """One ordering pair per adjacent card, or None if a pair cannot be explained."""
    pairs = set()
    for first, second in zip(codes, codes[1:]):
        limit = min(len(first), len(second))
        i = 0
        while i < limit and first[i] == second[i]:
            i += 1
        if i < limit:
            pairs.add((first[i], second[i]))
        elif len(first) > len(second):
            return None            # a longer code filed ahead of its own prefix
    return pairs


def solve(codes):
    letters = {ch for code in codes for ch in code}
    pairs = implied_pairs(codes)
    if pairs is None:
        return ""
    later = defaultdict(list)
    waiting = {ch: 0 for ch in letters}
    for before, after in pairs:
        later[before].append(after)
        waiting[after] += 1
    ready = [ch for ch in letters if waiting[ch] == 0]
    heapq.heapify(ready)
    placed = []
    while ready:
        # Invariant: every letter already placed has all of its predecessors
        # placed too, so the prefix built so far is a valid order on its own.
        ch = heapq.heappop(ready)
        placed.append(ch)
        for after in later[ch]:
            waiting[after] -= 1
            if waiting[after] == 0:
                heapq.heappush(ready, after)
    # A letter that never reaches zero sits on a cycle: no order explains the file.
    return "".join(placed) if len(placed) == len(letters) else ""

TESTS = [
    ((["dc", "da", "cab", "cb", "ab", "b"],), "dcab"),
    ((["mb", "ma"],), "bam"),                       # one constraint, the rest tie-broken
    ((["glaze", "gla"],), ""),                      # prefix filed after the longer code
    ((["tin", "nit", "tan"],), ""),                 # t before n and n before t
    ((["kiln", "kilt", "tarn", "tare", "one"],), "aiklnerto"),
    ((["zz"],), "z"),                               # one card, no pair to read
    ((["ab", "ab"],), "ab"),                        # equal neighbours imply nothing
    ((["b", "a", "c"],), "bac"),                    # the order is forced end to end
]

Pitfalls

• Recording only the differences. ["glaze", "gla"] has no differing position, so a loop that reacts to differences alone records nothing and returns a confident "aegilz". The missing difference is the contradiction.
• Seeding the letters from the arrows. m in ["mb", "ma"] appears in no fact, so a node set built while scanning pairs drops it and the answer comes back "ba" — one letter short.
• Counting a repeated arrow twice. Two pairs both saying c before a leave a stuck at in-degree one forever, and a consistent index reports a cycle. Collect the arrows in a set.

Variants

• Cycles and topological order — the peel used here, and why an order exists exactly when no cycle does.
• The tunnel to seal — a cycle you want to find rather than rule out.