Alien Dictionary

Problem

An unknown language uses lowercase Latin letters but sorts them in an order you do not know. You are given a list of words that is already sorted according to that language's alphabet. Recover a possible ordering of the letters that appear in the words. Return it as a string. If the given list is inconsistent with any ordering, return "". If several orderings are consistent, any one is acceptable.

• There are at most a few hundred words, each at most a few hundred characters.
• Every letter that appears in any word must appear exactly once in the output.
• Sorting rules match ordinary lexicographic comparison, including the rule that a string sorts before any longer string that has it as a prefix.

Examples

• words = ["psu","psg","is","iuu","sguu"] → "pisug". Comparing adjacent words gives u < g, p < i, s < u, i < s; the only order consistent with all of them is p i s u g.
• words = ["m","k","m"] → "". m < k from the first pair and k < m from the second: a contradiction.
• words = ["xyz","xy"] → "". A longer word appears before its own prefix, which no alphabet permits.

Hints

1. What does a single pair of adjacent words tell you? Only one fact, and only from one position.
2. Collect all such facts as directed edges between letters. What structure do consistent facts form, and what does an inconsistency look like?
3. Build a graph from the first differing character of each adjacent pair (watching for the prefix case), then topological sort; a cycle or an unsortable remainder means "".