Alien Dictionary
On this page
Problem statement
An alien language uses lowercase English letters, but in an unknown order. You get a list of words that is already sorted in that alien order. Return a string of all letters that appear, in an order consistent with the list. If no order can produce this sorting, return an empty string. If several orders work, return any of them.
A favorite at companies that like graph questions, because nothing in the prompt says "graph". The skill being tested is turning ordering clues into edges and then running a topological sort. Original problem: LeetCode 269 (premium).
Example

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Input: words = ["z", "x", "z"]
Output: "" # z before x and x before z: a cycle
Input: words = ["abc", "ab"]
Output: "" # a longer word cannot come before its own prefix
Constraints (assumed)
- 1 ≤ number of words ≤ 100, each 1 to 100 lowercase letters.
- Letters that appear in no rule can go anywhere in the output.
What this question tests
- Modeling: seeing letters as nodes and "comes before" clues as directed edges.
- Topological sort, including cycle detection.
- Careful reading of the comparison rule: only the first difference counts, and the prefix case is invalid input.
Questions to ask first
- If several orders are valid, can I return any? (Yes.)
- Should letters with no rules appear in the output? (Yes, every letter that appears in any word.)
- What if the input is inconsistent? (Return
"". Confirm this, since some versions ask you to raise an error.) - Can the same word appear twice in a row? (Yes; it gives no rule and is not an error.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.