269. Alien Dictionary

Practice Alien Dictionary for free on NudgeCode: Hard, Graph pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

An alien language uses lowercase English letters, but in an order you don't know. You get a list words that is said to be sorted in that language's dictionary order. Words are compared letter by letter: the first position where two words differ decides which comes first, and if one word is a prefix of the other, the shorter word comes first.

Return a string containing every letter that appears in words exactly once, ordered so that the list is sorted under that order. If several orders work, return any of them; the expected value is one of them. Letters with no rule between them can go in any order.

If no order can make the list sorted, return "". That happens when the rules contradict each other, or when a word comes before a word that is its own proper prefix (like "abc" before "ab").

Example

words = ["wrt","wrf","er","ett","rftt"]  ->  "wertf"
words = ["z","x","z"]                   ->  ""

Constraints