239. Alien Dictionary
A newly discovered language writes with the ordinary lowercase letters a–z, but ranks them in its own unknown order. You receive a list of words words that is claimed to be sorted lexicographically according to that alien ranking.
Recover a ranking of the letters and return it as a string containing every letter that appears in words, exactly once. Two rules make the answer well-defined:
- When several rankings are consistent with the words, return the one that comes first in normal alphabetical order.
- If no ranking can explain the list (the comparisons contradict each other, or a word is followed by its own proper prefix), return the empty string
"".
Remember how dictionary order works: two words are compared at their first differing position, and a shorter word precedes any longer word it prefixes.
Example 1:
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Explanation: Adjacent pairs give t<f (wrt/wrf), w<e (wrf/er), r<t (er/ett) and e<r (ett/rftt). Chaining them forces the unique order w, e, r, t, f.
Example 2:
Input: words = ["z", "x"]
Output: "zx"
Explanation: The only comparison says z ranks before x, so the ordering is "zx".
Example 3:
Input: words = ["z", "x", "z"]
Output: ""
Explanation: The pairs demand z<x and x<z at the same time — a contradiction, so no ranking exists.
Constraints:
- 1 ≤ words.length ≤ 100
- 1 ≤ words[i].length ≤ 100
- words[i] consists only of lowercase English letters.
- When several orderings are valid, the required answer is the alphabetically smallest one.
Hints:
Only adjacent words carry information: the first position where a pair differs says one letter ranks before another. Everything after that position tells you nothing.
Those before/after facts are directed edges between letters — the answer is a topological order of that graph, and a cycle means the input lies.
Watch the pair with no differing position: if the earlier word is longer (e.g. "abc" before "ab"), the list is invalid.
To get the alphabetically smallest valid order, run Kahn's algorithm but always take the smallest currently-available letter — a min-heap of indegree-0 letters does exactly that.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Expected output: "wertf"