Hints — p69 Alien Dictionary

Hint 1. You’re given lex-sorted words in an unknown alphabet; derive an alphabet order. Pattern: topological sort over a graph of characters. The trick: you must INFER the edges from the word list.

Hint 2. For each adjacent pair words[i], words[i+1], find the first differing character: that gives ONE edge (w1[j] → w2[j]). STOP comparing after that — later characters give NO ordering information.

Hint 3. Prefix-violation edge case: if words[i] is longer than words[i+1] AND words[i+1] is a prefix of words[i] (e.g., ["abc","ab"]), the input is impossible — return "".

Hint 4. Build the graph; collect all distinct characters (not just edge endpoints — isolated chars must still appear in the output). Run Kahn’s BFS topo sort: start with all chars of indeg 0, pop and append, decrement neighbors.

Hint 5. Cycle detection: if the final ordering’s length is less than the number of distinct characters, there’s a cycle — return "". The three failure modes (prefix violation, cycle, missing chars) are independent; test each.

If stuck: see solution.py.