Extraterrestrial Language

You're given a list of words, all written in some unknown alien language, and you're told that the list is sorted in that language's dictionary order. From those words alone, infer the alphabet — the order of the letters that explains the sort. This is LeetCode 269 "Alien Dictionary". The output is a string of every distinct character used in the input, arranged so that the input's order is consistent with it.

The order is not always unique — many valid alphabets can explain the same word list — and your function may return any one of them. If the input is inconsistent (cyclic constraints, or a longer word appearing before its own prefix), return the empty string.

Signature

function alienOrder(words: string[]): string;

Examples

// LeetCode classic — one valid order is 'wertf'.
alienOrder(['wrt', 'wrf', 'er', 'ett', 'rftt']);
// → 'wertf' (or any other valid topological order over {w, e, r, t, f})

// A single word constrains nothing. Any permutation of its characters is valid.
alienOrder(['hello']);
// → e.g. 'helo' (or 'hloe', etc. — order across these four chars is unspecified)

// All-same words — only one distinct character, so only one possible result.
alienOrder(['z', 'z', 'z']);
// → 'z'

// Prefix violation: 'ab' is a prefix of 'abc', so 'abc' cannot come first.
alienOrder(['abc', 'ab']);
// → '' (impossible in any dictionary order)

// Cyclic constraint: z must come before x (from pair 1), then x must come before z (from pair 2).
alienOrder(['z', 'x', 'z']);
// → '' (the resulting graph has a cycle)

Notes

• Multiple valid orders are acceptable. If two different orders both explain the input, return any one of them. Tests verify structural validity (every input adjacency is respected) rather than exact string equality.
• Every character that appears in the input must appear in the output exactly once — including characters that have no ordering constraints relative to others.
• Empty input returns the empty string ''.
• Prefix violation — when one word is a strict prefix of the previous word (e.g. ['abc', 'ab']), no dictionary order can explain that ordering. Return ''.
• Cycle in the derived constraints — return ''. A cycle means the input is self-contradictory.
• Don't mutate the input array.