Alien Dictionary Smallest Order
01 · Problem
An alien language uses a subset of the lowercase English letters, but in an unknown order. You receive a list words that is claimed to be sorted lexicographically according to the alien alphabet (with the usual rule that a proper prefix sorts before any longer word that extends it).
Return a string containing every distinct letter that appears in words, each exactly once, in an order consistent with that sorting. Letters not appearing in words must not be included.
Usually several orders are consistent. To make the answer unique, return the lexicographically smallest valid order under the normal English alphabet. If no order can make words sorted (for example, the constraints contradict each other, or a word appears after a longer word that it is a prefix of), return the empty string "".
02 · Examples
words = ["ba","bc","ac","cab"]
"bac"
Comparing "ba"/"bc" gives a < c, and "bc"/"ac" gives b < a. The only order containing all three letters is b, a, c.
words = ["zx","zy","yx"]
"xzy"
The rules are x < y (from "zx"/"zy") and z < y (from "zy"/"yx"). Both "xzy" and "zxy" are valid; "xzy" is lexicographically smaller.
words = ["abc","ab"]
""
"ab" is a proper prefix of "abc" but comes after it, which no alphabet can explain.
03 · Constraints
- 011 <= words.length <= 100
- 021 <= words[i].length <= 100
- 03words[i] consists only of lowercase English letters
04 · Optimal complexity
- Time
- O(C + U^2)
- Space
- O(U^2)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.