Alien Dictionary
WHAT IT SAYS
Given words sorted by an unknown alphabet, recover a valid ordering of that alphabet's characters (or report that none exists).
WHAT IT'S REALLY ASKING
"A sorted word list is a pile of testimony, and each adjacent pair testifies to exactly ONE fact: at their first differing position, the first word's letter precedes the second's — everything after that position is noise, decided already. Extract one edge per adjacent pair, and the exotic decoding problem collapses into the topological sort you already own."
Search over alphabets, validating each
O(k! · total word length) — factorial in the alphabet sizeEnumerate candidate orderings of the characters that appear, and for each, check whether the given word list is sorted under it; return any ordering that passes.
WHERE THE WORK IS WASTED — Generate-and-test at its most wasteful: the word list doesn't merely VALIDATE orderings, it CONSTRAINS them, and the constraints are sitting in plain sight — each adjacent word pair pins down one precedence the search keeps rediscovering by failing. Worse, validation re-derives the same facts per candidate: every tested alphabet re-compares the same word pairs, re-finding the same first-difference positions, only to throw the information away with the rejected candidate. The constraints should be extracted ONCE, as data, and handed to a solver that assembles an order directly — which is precisely what topological sort is.
Adjacent pairs, first difference only. The rest is noise.
Two compressions turn the word list into a small graph, and each has a proof. Compression one: only ADJACENT pairs matter. Sortedness of a list is equivalent to sortedness of every adjacent pair — word[i] ≤ word[i+1] for all i chains, by transitivity of the order, into word[i] ≤ word[j] for all i < j. So comparing all O(n²) pairs extracts nothing the O(n) adjacent comparisons didn't already imply; the non-adjacent constraints are theorems, not data. Compression two: within one pair, only the FIRST differing position speaks. Lexicographic comparison is decided at the earliest mismatch — everything before it is equal (contributing nothing), and everything after it is unconstrained BY THIS PAIR, because the earlier position already settled the comparison regardless of what follows. So each adjacent pair yields at most ONE edge: firstDiffChar(w1) → firstDiffChar(w2). A thousand words of testimony compress to at most n-1 edges over at most 26 nodes. One pair yields zero edges in two very different ways, and telling them apart is the problem's hidden test: identical-prefix pairs where the first word is SHORTER ('ab' before 'abc') are consistent with every alphabet — no edge, fine. But the first word LONGER ('abc' before 'ab') is a contradiction with lexicographic order itself — a proper prefix precedes its extension under ANY alphabet — so the input is invalid regardless of character precedences. Report failure immediately; no graph can absolve it. Miss this and the topo sort cheerfully returns a wrong answer. What remains is Course Schedule verbatim: nodes are the characters that appear anywhere (including constraint-free ones — they must still be emitted), edges are the mined precedences, and Kahn's peeling either consumes all k characters (any pop-order is a valid alphabet — the answer is generally not unique, and that slack is fine) or stalls, certifying contradictory testimony: a precedence cycle like a<b, b<c, c<a. Both failure modes — the prefix violation and the cycle — are 'no valid alphabet', but they fail at different stages, and clean code checks them where they live.
One pass of adjacent comparisons, then Kahn
O(total word length + k + E) time — the comparisons dominate — O(k + E) graph spaceRegister every character of every word as a node. For each adjacent word pair: scan to the first mismatch — found: add that single edge (deduplicate; parallel edges inflate in-degrees) and stop scanning the pair; no mismatch and the first word is longer: return failure. Then Kahn's peeling over the character graph: all k popped → join them into the answer; fewer → cycle → failure.
Sortedness Is Testimony
YOU'LL SEE IT AGAIN WHEN
- Input is stated to be SORTED under an unknown or partial order — the sorting itself encodes the constraints you must recover.
- Transitivity makes non-adjacent comparisons redundant, and per-comparison only the first difference constrains — extraction is small and exact.
- Degenerate testimony splits into 'no information' (prefix, consistent) and 'inherent contradiction' (longer word first) — the latter fails before any graph is built.