Alien Dictionary Solutions & Complexity

1. Define the problem

Alien Dictionary

You are given a list of words from an alien language, already sorted lexicographically according to that language's unknown alphabet. Return a string of every unique letter in a valid alphabet order, or an empty string if the order is impossible or the input is invalid. Compare each pair of neighboring words letter by letter — the first place they differ tells you one letter must come before another. Collect those edges, then topologically sort the letters .

Constraints

1 ≤ words.length ≤ 100
1 ≤ words_i.length ≤ 100
words_i consists of lowercase English letters

Example

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

Output"wertf"

Explanation Comparing neighboring words gives the edges t→f, w→e, r→t, e→r, which sort to w, e, r, t, f.

2. Know the words first

In plain terms

Lexicographically sorted: Ordered the way a dictionary would, comparing words letter by letter using the alphabet's own order.
Invalid input: A longer word appearing before its own prefix (like 'abc' before 'ab') can never happen in a correctly sorted dictionary, so it signals the input itself is broken.

3. Visualize the solution

Derive edges from adjacent words, then topologically sort the letters

Statuscompare wrt, wrf

First difference at index 2: t vs f — edge t→f. In-degree so far: f=1.

What happens in this step

compare "wrt" vs "wrf"
  index 0: w == w
  index 1: r == r
  index 2: t != f  → first difference

edge: t → f

in-degree[f] = 0 → 1

The first mismatch between neighboring words always gives one ordering edge. Here it says t must come before f in the alien alphabet, so f's in-degree rises to 1.

Step 1 of 4

Steps to visualize

Compare each pair of neighboring words letter by letter; the first mismatch gives an edge from the earlier word's letter to the later word's letter.
If one word is a prefix of the next, no edge is added — but if the longer word comes first, the input is invalid.
Run Kahn's algorithm over the resulting letter graph: queue up letters with in-degree zero and peel them off.
If every letter gets placed, the result is a valid alien alphabet order; otherwise a cycle makes the input invalid.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Derive edges from adjacent words, then topologically sort the letters

Statuscompare wrt, wrf

First difference at index 2: t vs f — edge t→f. In-degree so far: f=1.

What happens in this step

compare "wrt" vs "wrf"
  index 0: w == w
  index 1: r == r
  index 2: t != f  → first difference

edge: t → f

in-degree[f] = 0 → 1

The first mismatch between neighboring words always gives one ordering edge. Here it says t must come before f in the alien alphabet, so f's in-degree rises to 1.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function alienOrder(words) {
  const graph = new Map();
  const inDegree = new Map();

  for (const word of words) {
    for (const ch of word) {
      if (!graph.has(ch)) {
        graph.set(ch, new Set());
        inDegree.set(ch, 0);
      }
    }
  }

  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i];
    const w2 = words[i + 1];
    const minLen = Math.min(w1.length, w2.length);
    let foundDifference = false;

    for (let j = 0; j < minLen; j++) {
      if (w1[j] !== w2[j]) {
        if (!graph.get(w1[j]).has(w2[j])) {
          graph.get(w1[j]).add(w2[j]);
          inDegree.set(w2[j], inDegree.get(w2[j]) + 1);
        }
        foundDifference = true;
        break;
      }
    }

    if (!foundDifference && w1.length > w2.length) {
      return '';
    }
  }

  let queue = [];
  for (const [ch, degree] of inDegree) {
    if (degree === 0) {
      queue.push(ch);
    }
  }
  queue.sort();

  let order = '';

  while (queue.length > 0) {
    queue.sort();
    const ch = queue.shift();
    order += ch;
    for (const next of graph.get(ch)) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) {
        queue.push(next);
      }
    }
  }

  return order.length === inDegree.size ? order : '';
}

Time: O(total characters + unique letters)
Space: O(unique letters)

6. Test cases

Test cases

Input	Expected	Covers
`words = ["wrt","wrf","er","ett","rftt"]`	`"wertf"`	the classic worked example with a five-letter chain
`words = ["z","x","z"]`	`""`	z and x each require the other, an impossible order
`words = ["abc","ab"]`	`""`	a longer word appearing before its own prefix is invalid input
`words = ["abc"]`	`"abc"`	only one word, so there are no ordering constraints at all
`words = ["abc","abc"]`	`"abc"`	duplicate neighboring words add no edge and are still valid
`words = ["ac","ab","zc","zb"]`	`"acbz"`	edges from two independent word pairs combine into one order
`words = ["ab","xy"]`	`"abxy"`	a small graph with letters that have no constraints between them
`words = ["a","b","c","a"]`	`""`	a three-letter cycle formed across more than two neighboring pairs

Alien Dictionary