Alien Dictionary

Free with account Updated Nov 19, 2026 · 7 min read
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

    From the sorted list wrt, wrf, er, ett, rftt you can infer the order w, e, r, t, f.
    From the sorted list wrt, wrf, er, ett, rftt you can infer the order w, e, r, t, f.
    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

    1. If several orders are valid, can I return any? (Yes.)
    2. Should letters with no rules appear in the output? (Yes, every letter that appears in any word.)
    3. What if the input is inconsistent? (Return "". Confirm this, since some versions ask you to raise an error.)
    4. Can the same word appear twice in a row? (Yes; it gives no rule and is not an error.)