Skip to main content

269. Alien Dictionary

hardAsked at Airbnb

Given a list of words sorted lexicographically in some unknown alphabet, derive the order. Airbnb asks this to test inferring a directed graph from pairwise word comparisons plus topological sort.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb senior+ onsite reports consistently include this as a signature graph hard.
  • Blind (2025-12)— Recurring in Airbnb backend and platform team interviews.

Problem

There is a new alien language that uses the English 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 in 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. If no such ordering exists, return an empty string. If there are multiple valid orderings, return any of them.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of only lowercase English letters.

Examples

Example 1

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

Example 2

Input
words = ["z","x"]
Output
"zx"

Example 3

Input
words = ["z","x","z"]
Output
""

Explanation: z < x < z is a cycle.

Approaches

1. Build graph from adjacent pairs + Kahn's BFS (optimal)

For each adjacent pair, find the first differing char to derive one edge. Edge case: if word_i is a prefix of word_{i+1} but longer, return ''. Then topological-sort.

Time
O(N + sum of word lengths)
Space
O(1) — alphabet is bounded
function alienOrder(words) {
  const graph = new Map();
  const indeg = new Map();
  for (const w of words) for (const c of w) { graph.set(c, graph.get(c) || new Set()); indeg.set(c, indeg.get(c) || 0); }
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i], b = words[i + 1];
    if (a.length > b.length && a.startsWith(b)) return '';
    for (let k = 0; k < Math.min(a.length, b.length); k++) {
      if (a[k] !== b[k]) {
        if (!graph.get(a[k]).has(b[k])) { graph.get(a[k]).add(b[k]); indeg.set(b[k], indeg.get(b[k]) + 1); }
        break;
      }
    }
  }
  const queue = [];
  for (const [c, d] of indeg) if (d === 0) queue.push(c);
  let order = '';
  while (queue.length) {
    const u = queue.shift();
    order += u;
    for (const v of graph.get(u)) {
      indeg.set(v, indeg.get(v) - 1);
      if (indeg.get(v) === 0) queue.push(v);
    }
  }
  return order.length === indeg.size ? order : '';
}

Tradeoff: Clean two-phase solution: derive edges from pairwise comparisons, then topological-sort. The prefix-conflict check is the edge case most candidates miss.

2. DFS post-order topological sort

Same graph extraction; DFS with 3-color cycle detection; reverse post-order is the answer.

Time
Same
Space
Same
function alienOrderDFS(words) {
  const graph = new Map();
  for (const w of words) for (const c of w) graph.set(c, graph.get(c) || new Set());
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i], b = words[i + 1];
    if (a.length > b.length && a.startsWith(b)) return '';
    for (let k = 0; k < Math.min(a.length, b.length); k++) {
      if (a[k] !== b[k]) { graph.get(a[k]).add(b[k]); break; }
    }
  }
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Map();
  for (const c of graph.keys()) color.set(c, WHITE);
  const stack = [];
  let cycle = false;
  function dfs(u) {
    color.set(u, GRAY);
    for (const v of graph.get(u)) {
      if (color.get(v) === GRAY) { cycle = true; return; }
      if (color.get(v) === WHITE) { dfs(v); if (cycle) return; }
    }
    color.set(u, BLACK);
    stack.push(u);
  }
  for (const c of graph.keys()) if (color.get(c) === WHITE) { dfs(c); if (cycle) return ''; }
  return stack.reverse().join('');
}

Tradeoff: Same idea, different idiom. Reverse-post-order DFS is the textbook approach; Kahn's BFS is usually easier to whiteboard.

Airbnb-specific tips

Airbnb's bar is articulating two things: (1) edges come from the first differing char of adjacent words; (2) the prefix conflict ('abc' before 'ab') is an immediate fail. Most candidates miss the prefix conflict. Mention it before any code: 'If a longer word appears before its prefix, that's impossible — return empty.'

Common mistakes

  • Forgetting the prefix-conflict edge case ('abc' before 'ab').
  • Adding multiple edges from a single pair (only the first differing char gives an edge).
  • Not including ALL letters in the graph — even isolated ones must appear in the output.

Follow-up questions

An interviewer at Airbnb may pivot to one of these next:

  • Verifying Alien Dictionary (LC 953) — given the order, verify the dictionary is sorted.
  • Course Schedule II (LC 210) — same topological-sort template.
  • What if there could be ties (some letters with no relative order)? (Multiple valid outputs.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does only the FIRST differing char give an edge?

Lex order is decided at the first differing position. Later chars don't constrain anything — 'abx' before 'aby' tells us nothing about x and y because the order was already decided by position 2.

Are all 26 letters in the output?

Only letters that appear in at least one word. The output length equals the number of distinct letters used.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Alien Dictionary and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →