01. Alien Dictionary

Difficulty:HardPattern:Topological Sort / Kahn BFSTime:O(V + E)Space:O(V + E)

There is a new alien language that uses the Latin alphabet. However, the order among the letters is unknown to you. You are given a list of strings words from the alien language's dictionary, where the strings inside words are sorted lexicographically by the rules of this new language. Return a string of the unique letters in the new alien language sorted in lexicographically increasing order.

How It Works & Algorithmic Design

Solves using Directed Graph Construction with Kahn's Topological Sort:

Graph Nodes: Initialize adjacency list adj and in-degree map inDegree for every unique character.
Edge Construction: Compare adjacent words word1 and word2:
- Find first mismatch index $k$: char1 = word1[k], char2 = word2[k].
- Add directed edge char1 -> char2 and increment inDegree[char2]++.
- Edge Case: if word2 is a prefix of word1 (e.g., "abc" before "ab"), language order is invalid $\to$ return "".
Kahn's BFS: Process nodes with inDegree === 0 using a queue.
Cycle Detection: If result length does not match total unique characters, a cycle exists $\to$ return "".

Why This Approach Works Best

Topological sorting detects illegal circular dependencies while producing a valid linear character ordering in $O(V + E)$ time.

Example Walkthrough

Input: words = ["wrt","wrf","er","ett","rftt"]

Sorted alien words list.

Extracted Rules: 't'->'f', 'w'->'e', 'r'->'t', 'e'->'r'

Character ordering graph edges.

Output: "wertf"

Valid alien alphabet order.

Answer: Alien Dictionary Topological Sort implementation

function alienOrder(words) {
  const adj = {}, inDegree = {};
  for (const w of words) {
    for (const c of w) {
      inDegree[c] = 0;
      adj[c] = new Set();
    }
  }
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    if (w1.length > w2.length && w1.startsWith(w2)) return '';
    for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
      if (w1[j] !== w2[j]) {
        if (!adj[w1[j]].has(w2[j])) {
          adj[w1[j]].add(w2[j]);
          inDegree[w2[j]]++;
        }
        break;
      }
    }
  }
  const queue = [];
  for (const c in inDegree) if (inDegree[c] === 0) queue.push(c);
  let res = '';
  while (queue.length) {
    const c = queue.shift();
    res += c;
    for (const neighbor of adj[c]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return res.length === Object.keys(inDegree).length ? res : '';
}

💡 Build graph edges from adjacent word differences and perform Kahn's BFS topological sort.

Key Takeaways

Extract character dependency directed edges by comparing adjacent words.
Prefix check (e.g. "abc" before "ab") catches illegal invalid input dictionary states.
Runs in $O(V + E)$ time where $V$ is unique characters and $E$ is extracted ordering rules.