Solution

You'll reconstruct an unknown alphabet from a list of words that are claimed to be sorted in that alphabet's order, by deriving pairwise letter-ordering constraints from adjacent word comparisons and then topologically sorting the resulting graph.

The problem, in plain English

Pretend a friend hands you a sheet from an alien dictionary and tells you, "these words are listed in alphabetical order, can you figure out their alphabet?" Each pair of adjacent words on the sheet leaks one tiny fact about the alphabet — the first letter where they disagree tells you which of those two letters comes first. Stitch enough of those facts together and you can reconstruct a consistent ordering of all the letters that appear. The output is a string listing every letter exactly once, in some order that's consistent with the dictionary.

There are two ways the input can be inconsistent. One: the constraints form a cycle (z must come before x AND x must come before z) — no linear order can satisfy both. Two: a longer word appears before its own prefix (['abc', 'ab']) — in any dictionary, a strict prefix comes first, so this ordering is impossible no matter what alphabet you pick. In either case you return the empty string.

The mental model

The whole problem is a graph problem in disguise. Each distinct character is a node. Each adjacent word pair contributes at most one directed edge. Topologically sort the resulting graph and you have your alphabet — or you discover the graph has a cycle and you bail.

The key insight for step 2 is that only the first differing character between two adjacent words carries any ordering signal. Take 'wrt' and 'wrf'. Positions 0 and 1 match (both w, both r), so they tell us nothing. Position 2 disagrees — 't' on the left, 'f' on the right — and that's where the sort order kicks in: t must come before f. Everything after position 2 is unconstrained by this pair, because the comparator stopped reading once it found a difference. Compare past the first divergence and you'll manufacture edges that aren't real.

The prefix-violation case is the sneaky one. If 'abc' appears before 'ab', comparing character by character would scan through positions 0 and 1 (both match), then run off the end of 'ab' without finding any differing character. The loop exits with no edge added — but the input is still invalid. In any real dictionary, a strict prefix sorts FIRST. We need an explicit guard: if a.length > b.length && a.startsWith(b), return '' immediately.

Step 3 — the topological sort — uses Kahn's algorithm: a BFS that starts from every node with indegree 0 (no incoming edges, so nothing has to come before it), pops a node, "removes" its outgoing edges by decrementing each successor's indegree, and pushes any successor that just hit zero. When the queue drains, either we emitted every node (success) or some nodes were never freed because their indegrees never reached zero (cycle).

A first attempt

Two naive ideas come up immediately. Both teach something about why the working solution looks the way it does.

Attempt 1 — compare every pair of words, not just adjacent ones. The naive instinct is "more comparisons → more constraints → more accurate ordering." Try it on ['z', 'x', 'y']:

function alienOrderTooManyPairs(words) {
  // ...build the char set...
  for (let i = 0; i < words.length; i++) {
    for (let j = i + 1; j < words.length; j++) {
      // derive edge from words[i] and words[j]
    }
  }
  // ...topological sort...
}

The non-adjacent pair ('z', 'y') produces an edge z → y. But that edge is weaker than the two adjacent edges z → x and x → y we'd already derive — it's implied by them transitively. Worse, on inputs where two non-adjacent words don't share an ordering relationship that's actually derivable from the dictionary contract (e.g. on ['zb', 'xa', 'yc'], the pair ('zb', 'yc') would give us z → y, but the real chain is only z → x and x → y, no direct z → y edge is part of the alphabet inference), you can manufacture spurious edges that turn a valid input into a fake cycle. The dictionary's pairwise contract holds only between adjacent words; reach beyond adjacency and you're inventing constraints the input doesn't support.

Attempt 2 — sort the characters by frequency, or by first appearance in the input. This one's tempting because it requires no graph at all:

function alienOrderByFirstAppearance(words) {
  const seen = [];
  const set = new Set();
  for (const w of words) for (const ch of w) {
    if (!set.has(ch)) { set.add(ch); seen.push(ch); }
  }
  return seen.join('');
}

The problem is that alphabet order has nothing to do with how often a character appears or when it first shows up. On ['cba', 'cab'], the characters first appear in the order c, b, a — but the actual constraint from the pair (first diff at index 1: b vs a) says b → a. The "first appearance" output would be 'cba', which puts b before a correctly by accident, but on a longer input the heuristic breaks immediately. Frequency-based ordering is worse — characters that appear once each can still have a clean order, and characters that appear many times can be anywhere.

Both attempts share a root cause: they don't engage with the structure of the dictionary contract. The contract is exclusively about adjacent pairs and exclusively about the first differing character. Anything else is noise.

The working solution

function alienOrder(words) {
  if (words.length === 0) return '';

  // adj : char → Set of chars that come immediately after it.
  //       Using a Set auto-deduplicates the same edge derived from multiple pairs
  //       (e.g. ['ab', 'ac', 'ad'] does not add the same edge a→c twice).
  // indegree : char → count of incoming edges. Tracked separately because Kahn's
  //            algorithm needs O(1) "how many predecessors does this node still
  //            have?" lookups; computing it from `adj` on each query would cost
  //            O(V + E) per check.
  const adj = new Map();
  const indegree = new Map();

  // Step 1 — gather every distinct character into the graph as a node with
  // empty adjacency and zero indegree. This must happen BEFORE we touch the
  // word pairs, because a character that has no ordering relation to any
  // other character (e.g. 'q' in ['abc', 'qbz']) must still end up in the
  // BFS queue with indegree 0. If we initialize indegrees lazily during the
  // pair loop, isolated chars silently disappear from the result.
  for (const w of words) {
    for (const ch of w) {
      if (!adj.has(ch)) {
        adj.set(ch, new Set());
        indegree.set(ch, 0);
      }
    }
  }

  // Step 2 — derive edges from adjacent word pairs.
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i];
    const b = words[i + 1];

    // Prefix-violation guard. If `a` is strictly longer than `b` and `a`
    // starts with `b`, no dictionary order can place `a` before `b`. The
    // inner mismatch loop below would scan to min(a.length, b.length),
    // find no difference, exit silently, and we'd return a bogus order.
    if (a.length > b.length && a.startsWith(b)) return '';

    // Find the FIRST differing character. Only that position contributes
    // an ordering constraint; characters after the first divergence are
    // unconstrained by this pair (their relative order is decided by some
    // other pair, or not at all).
    for (let j = 0; j < Math.min(a.length, b.length); j++) {
      if (a[j] !== b[j]) {
        // Add edge a[j] → b[j], but only if it's new. The `has` check
        // matters because the same edge can be derived from multiple
        // pairs (think ['ab', 'ac', 'ad'] — three pairs but the same
        // a → c relationship is derivable once, not three times).
        // Double-counting would inflate the indegree and leave a node
        // permanently stuck above zero, falsely flagging a cycle.
        if (!adj.get(a[j]).has(b[j])) {
          adj.get(a[j]).add(b[j]);
          indegree.set(b[j], indegree.get(b[j]) + 1);
        }
        // Break — characters past the first diff carry no info from
        // THIS pair. Continuing the loop would insert spurious edges.
        break;
      }
    }
  }

  // Step 3 — Kahn's algorithm. Seed the BFS with every char that has no
  // incoming edges (nothing has to come before it).
  const queue = [];
  for (const [ch, deg] of indegree) {
    if (deg === 0) queue.push(ch);
  }

  const result = [];
  while (queue.length > 0) {
    const ch = queue.shift();
    result.push(ch);
    // "Remove" each outgoing edge by decrementing the successor's
    // indegree. If a successor's count hits zero, all of its predecessors
    // have been emitted, so it's safe to emit next.
    for (const next of adj.get(ch)) {
      indegree.set(next, indegree.get(next) - 1);
      if (indegree.get(next) === 0) queue.push(next);
    }
  }

  // Cycle detection. If we couldn't emit every node, some indegrees never
  // reached zero — those nodes are in a cycle (or downstream of one).
  if (result.length !== adj.size) return '';
  return result.join('');
}

module.exports = { alienOrder };

The key shifts from the naive versions: we engage with the dictionary contract directly (adjacent pairs only, first diff only), we build a real graph rather than a list, and we use Kahn's algorithm both to produce the order AND to detect impossibility in one pass. The prefix-violation guard is the only edge case that the topological sort itself can't catch — it's a syntactic property of the input, not a property of the derived graph.

Walking through one call

Two traces show the algorithm under different conditions: the LeetCode classic input, and the prefix-violation edge case.

Trace 1 — alienOrder(['wrt', 'wrf', 'er', 'ett', 'rftt']).

Step 1 — gather characters. Walking the words, we see w, r, t, f, e. Five nodes, all with indegree 0, all with empty adjacency Sets.

Step 2 — compare adjacent pairs.

• ('wrt', 'wrf'): positions 0, 1 match (w, r). Position 2 differs (t vs f). Add edge t → f. indegree[f] = 1.
• ('wrf', 'er'): position 0 differs (w vs e). Add edge w → e. indegree[e] = 1.
• ('er', 'ett'): position 0 matches (e). Position 1 differs (r vs t). Add edge r → t. indegree[t] = 1.
• ('ett', 'rftt'): position 0 differs (e vs r). Add edge e → r. indegree[r] = 1.

Final graph: edges w → e, e → r, r → t, t → f. Indegrees: w = 0, e = 1, r = 1, t = 1, f = 1. The graph is a straight chain.

Step 3 — Kahn's.

The queue seeds with [w] (the only indegree-0 char). Pop w → emit, decrement indegree[e] to 0, push e. Pop e → emit, decrement indegree[r] to 0, push r. Pop r → emit, decrement indegree[t] to 0, push t. Pop t → emit, decrement indegree[f] to 0, push f. Pop f → emit. Queue empty.

result = ['w', 'e', 'r', 't', 'f'], length 5 equals adj.size (5), so we return 'wertf'.

Trace 2 — alienOrder(['abc', 'ab']).

Step 1 gathers a, b, c as nodes. Step 2 hits the pair ('abc', 'ab'): a.length is 3, b.length is 2, a.length > b.length, and 'abc'.startsWith('ab') is true. The guard fires immediately and returns ''. We never even reach the inner character loop. The function exits in O(min(|a|, |b|)) time.

Without that guard, the inner loop would scan positions 0 and 1 (both match), exit with no edge added, then proceed to Kahn's. Kahn's would happily emit some permutation of a, b, c — a string that looks valid but doesn't reflect the (impossible) constraint we silently dropped. The guard is load-bearing for correctness, not just for early termination.

Gotchas

• Only the FIRST differing character contributes ordering info. Continuing the inner loop past the first divergence inserts spurious edges. On ('wrt', 'wrf'), after position 2 (t vs f) you'd be staring at end-of-string in both words — but on ('abc', 'adx'), continuing past position 1 (b vs d) would manufacture an edge c → x that the dictionary contract never gave you. Break after the first mismatch.
• Initialize indegree for EVERY char up front, not lazily during the pair loop. A character that has no ordering relation to anyone else (e.g. 'q' in ['abc', 'qbz']) still needs to be in the indegree Map with value 0 so the seed loop puts it in the BFS queue. Initialize lazily and isolated chars silently disappear from the output, making result.length < adj.size and triggering a false "cycle" return of ''.
• The prefix-violation guard is mandatory. Without if (a.length > b.length && a.startsWith(b)) return '';, the inner mismatch loop on ('abc', 'ab') scans through both matching positions, finds no difference, exits cleanly, and we proceed to topo-sort a graph that has no edges between a, b, c. The output looks "valid" — some permutation of those chars — but the input was actually impossible. The guard is the only way to catch this; no amount of graph machinery downstream will detect it.
• Duplicate edges from multiple pairs. Consider ['ab', 'ac', 'ad']. Pair 1 gives b → c, pair 2 gives c → d. Now consider ['ab', 'ac', 'ab', 'ac']. Pair 1 gives b → c, pair 3 gives b → c AGAIN. If you blindly increment indegree without checking, indegree[c] ends up at 2 even though only one predecessor b actually exists. When Kahn's emits b, the decrement brings indegree[c] to 1, never to 0 — c is stuck, result.length < adj.size, you incorrectly return ''. The fix is the if (!adj.get(a[j]).has(b[j])) guard before the increment; the Set in adj does the deduplication.
• Cycle detection lives in the comparison result.length !== adj.size. Kahn's BFS naturally stalls when every remaining node has indegree ≥ 1, because they're all in a cycle (or downstream of one). The cleanest signal is "did we emit every node?" — if not, cycle. Don't try to detect the cycle "during" Kahn's; the post-loop length check is exact, simple, and runs in O(1).
• Empty array input returns ''. The early if (words.length === 0) return ''; handles this. Without it, the rest of the function would gather no characters, build no edges, and return the empty string via result.join('') anyway — so the guard is partly cosmetic. But it's a clear statement of contract at the top.
• DFS-based topological sort is a valid alternative. Recurse from each unvisited node, mark "currently on path" as gray and "fully processed" as black, push to the result on exit (post-order), then reverse. If you hit a gray node during recursion, you've found a back-edge — cycle. The two approaches produce different valid orderings on the same graph; either satisfies the spec.

Going further

• DFS-based topological sort with three-color cycle detection. Walk every WHITE node depth-first. Mark a node GRAY when you enter it and BLACK when you exit. On exit, push the node onto the result. If you ever encounter a GRAY node during the recursion, you've found a back-edge — return ''. Reverse the final list to get the topological order. The trade-off: DFS gives you a different valid order than Kahn's (Kahn's emits sources first; DFS emits sinks first then reverses), and DFS can blow the recursion stack on very long chains (50k+ nodes) where Kahn's is heap-allocated and safe.

• Enumerate ALL valid topological orders. The standard Kahn's loop emits one order — but for a graph with multiple indegree-0 nodes at any step, every choice of "which one to pop next" leads to a different valid ordering. A backtracking variant explores them all by, at each step, trying every node currently in the queue as the next emission, recursing, and then undoing the indegree decrements. The output is a list of all valid alphabets — useful for showing the user that the input is ambiguous, or for picking the lexicographically smallest order. Worst case it's factorial in the number of "free" nodes at each step (a graph with no edges has V! valid orders), so don't run this on large inputs.

• Lexicographically smallest topological order. Sometimes you want the one canonical answer rather than "any valid order." Replace the FIFO queue with a min-heap keyed on the character itself; every time multiple nodes are ready to be emitted, pop the smallest one. The asymptotic cost goes from O(V + E) to O((V + E) log V), which is fine for an alphabet (V ≤ 26 typically) and gives reproducible output across runs.

• Detect AND report the cycle's members. When Kahn's stalls with result.length < adj.size, the unemitted nodes are exactly the ones in cycles or reachable from a cycle. For a debugging interface, you'd return them: const cycleSet = new Set(adj.keys()); for (const ch of result) cycleSet.delete(ch); return [...cycleSet];. To narrow down to the actual cycle (not just "downstream of a cycle"), do a DFS from any unemitted node and track the recursion path — the moment you revisit a gray node, the slice of the path from that node to the current node is the cycle. Useful when you want to surface the conflicting word pairs to the user rather than just saying "invalid."