4.21.5 — Alien Dictionary

LeetCode 269 · Hard

The problem

You are given a list of words, sorted according to some unknown alphabet. Work out an ordering of the letters consistent with that sorting. Return "" if none exists, and any valid one if several do.

words = ["wrt","wrf","er","ett","rftt"]   →  "wertf"
words = ["z","x"]                         →  "zx"
words = ["z","x","z"]                     →  ""     (contradiction)

The pattern

This is a topological sort, and you already know how to do that (4.20.9). The hard part is a step earlier:

Where do the edges come from?

Two adjacent words in a sorted list tell you exactly one thing. Compare them character by character; at the first position where they differ, the letter in the earlier word comes before the letter in the later word.

"wrt" and "wrf"
 w=w, r=r, t≠f   →   t comes before f

And that is all they tell you. Everything after the first difference is unconstrained — "wrt" before "wrf" says nothing about any letter beyond position 2.

Only the first difference produces an edge. Continuing past it invents constraints that do not exist, and that is the most common wrong solution.

The invalid case that is easy to miss

If a word is a prefix of the previous word, the input is impossible.

["abc", "ab"]     →  invalid

In any dictionary ordering, a prefix comes before the longer word. "ab" must precede "abc", so this list is not sorted under any alphabet.

The loop finds no differing character, so without an explicit check you would silently accept it. Check it, and check it before the general case, because it is the input designed to catch you.

Note that ["ab", "abc"] is perfectly fine — the shorter word first is correct.

The solution

Python

from collections import defaultdict, deque

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj = {c: set() for word in words for c in word}      # every letter seen
        indegree = {c: 0 for c in adj}

        for first, second in zip(words, words[1:]):
            min_len = min(len(first), len(second))

            if len(first) > len(second) and first[:min_len] == second[:min_len]:
                return ""                                     # prefix violation

            for i in range(min_len):
                if first[i] != second[i]:
                    if second[i] not in adj[first[i]]:
                        adj[first[i]].add(second[i])
                        indegree[second[i]] += 1
                    break                                     # ONLY the first difference

        queue = deque(c for c in indegree if indegree[c] == 0)
        order = []

        while queue:
            c = queue.popleft()
            order.append(c)
            for nxt in adj[c]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return ''.join(order) if len(order) == len(adj) else ""   # short → a cycle

TypeScript

function alienOrder(words: string[]): string {
  const adj = new Map<string, Set<string>>();
  const indegree = new Map<string, number>();
  for (const w of words) for (const c of w) {
    if (!adj.has(c)) { adj.set(c, new Set()); indegree.set(c, 0); }
  }

  for (let k = 0; k + 1 < words.length; k++) {
    const a = words[k], b = words[k + 1];
    const minLen = Math.min(a.length, b.length);

    if (a.length > b.length && a.slice(0, minLen) === b.slice(0, minLen)) return "";

    for (let i = 0; i < minLen; i++) {
      if (a[i] !== b[i]) {
        if (!adj.get(a[i])!.has(b[i])) {
          adj.get(a[i])!.add(b[i]);
          indegree.set(b[i], indegree.get(b[i])! + 1);
        }
        break;
      }
    }
  }

  const queue: string[] = [];
  for (const [c, d] of indegree) if (d === 0) queue.push(c);

  const order: string[] = [];
  let head = 0;
  while (head < queue.length) {
    const c = queue[head++];
    order.push(c);
    for (const nxt of adj.get(c)!) {
      indegree.set(nxt, indegree.get(nxt)! - 1);
      if (indegree.get(nxt) === 0) queue.push(nxt);
    }
  }

  return order.length === adj.size ? order.join('') : "";
}

Four details that decide correctness.

Seed every letter that appears anywhere, even letters with no constraints at all. A letter appearing in only one word still belongs in the output; forget it and the length check fails and you wrongly return "".

break after the first difference. The whole modelling step is in that one word.

adj holds sets, not lists, so a repeated constraint does not inflate the indegree. Two word pairs may both imply t → f, and counting it twice would leave f permanently blocked.

The final length check catches cycles, exactly as in 4.20.8. ["z","x","z"] gives z → x and x → z, neither reaches indegree 0, and the order comes out empty.

Trace

["wrt","wrf","er","ett","rftt"]

pair	first difference	edge
wrt, wrf	position 2: t vs f	t → f
wrf, er	position 0: w vs e	w → e
er, ett	position 1: r vs t	r → t
ett, rftt	position 0: e vs r	e → r

Letters: w, r, t, f, e. Indegrees: w = 0, everything else 1.

Kahn's: w → then e → then r → then t → then f. Result "wertf" ✓.

Complexity

O(C) where C is the total number of characters across all words. Building the graph is one pass over adjacent pairs, and the topological sort is O(V + E) with at most 26 letters and 26² edges — both constants.

Space O(1) in the alphabet, or O(V + E) stated generally.

Where this goes next

• Sequence Reconstruction — is the topological order unique? Yes exactly when the queue never holds more than one node.
• Verifying an Alien Dictionary (LeetCode 953) — the reverse: given the alphabet, check whether the words are sorted. Much easier, and a good warm-up.
• Version sorting, collation, locale-aware comparison — real systems face this. Unicode collation defines an ordering per locale, which is why ä sorts differently in German and Swedish. The alphabet really is data, not a constant.

What the interviewer will push on

"Where do the edges come from?" The first differing character between adjacent words, and nothing after it. This is the question the problem exists to ask.

"What if a word is a prefix of the previous one?" Invalid input, return "". If they do not ask, volunteer it.

"What if a letter has no constraints?" It must still appear in the output — seed every letter you see.

"How do you detect a contradiction?" A cycle, caught by the short-order check.

"Is the answer unique?" Usually not. Any valid topological order is accepted, and it is unique only when the queue never holds two letters at once.

"Why sets rather than lists in the adjacency map?" Duplicate constraints would inflate the indegree and deadlock the sort.

One thing to volunteer: say up front that the difficulty is building the graph, not sorting it. "Once I have the edges, this is Course Schedule II." That framing shows you decomposed the problem rather than met a new one.

Next: 4.21.6 Cheapest Flights Within K Stops — where Dijkstra gives the wrong answer and you have to know why.