Skip to main content

23. Alien Dictionary

hardAsked at GitLab

Given words sorted by an unknown alphabet, recover any valid alphabet order or return '' if impossible.

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

Problem

You are given a list of words sorted lexicographically by a foreign alphabet. Derive the order of letters in that alphabet. If the order is inconsistent (cycle) or impossible (prefix violation), return an empty string. Any valid order is acceptable.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • All characters are lowercase English letters

Examples

Example 1

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

Example 2

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

Approaches

1. DFS topological sort

Build edges from adjacent-word comparisons, DFS each unvisited letter, push to a stack on finish; reverse for the order. Reject cycles with gray markers.

Time
O(C)
Space
O(1) alphabet bound
/* For each adjacent pair, find first differing char and add edge a->b. Reject when shorter prefix follows longer with same prefix. DFS with gray/black sets, push on finish, reverse at end. */

Tradeoff:

2. Kahn's BFS over letter DAG

Compare adjacent words to find the first differing letter pair and add a directed edge. Then run Kahn's algorithm with in-degree zero queue. If the result skips a letter, the order is inconsistent.

Time
O(C)
Space
O(1) alphabet bound
function alienOrder(words){
  const g = new Map(), inDeg = new Map();
  for (const w of words) for (const c of w){ if (!g.has(c)){ g.set(c, new Set()); inDeg.set(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 j = 0; j < Math.min(a.length, b.length); j++){
      if (a[j] !== b[j]){
        if (!g.get(a[j]).has(b[j])){
          g.get(a[j]).add(b[j]);
          inDeg.set(b[j], inDeg.get(b[j]) + 1);
        }
        break;
      }
    }
  }
  const q = [];
  for (const [c, d] of inDeg) if (d === 0) q.push(c);
  let out = '';
  while (q.length){
    const u = q.shift();
    out += u;
    for (const v of g.get(u)) if (inDeg.set(v, inDeg.get(v) - 1).get(v) === 0) q.push(v);
  }
  return out.length === inDeg.size ? out : '';
}

Tradeoff:

GitLab-specific tips

GitLab uses this as the deepest topological-sort probe — the alien letter DAG is isomorphic to inferring stage ordering from observed CI-job completion sequences across a runner pool.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →