Alien Dictionary

An alien language is written with lowercase English letters, but its alphabet uses an order you do not know. You are given a list words that is claimed to be sorted in that alien order. Words compare the usual dictionary way: at the first position where two words differ, the word with the earlier letter comes first; if one word is a prefix of the other, the shorter word comes first.

Return a string containing every distinct letter that appears in words, each exactly once, arranged in an order under which words really is sorted. If several orders work, return any of them. If no order can make the list sorted, return the empty string "".

Example 1

Example 2

Example 3

Constraints

• 1 <= words.length <= 2000
• 1 <= words[i].length <= 100
• words[i] consists of lowercase English letters.
• Tests use at most 7 distinct letters, so every valid order can be checked.

Pattern Path · Graphs: Ordering & Union-Find · problem 145 of 169

Start simple

Try every permutation of the distinct letters and check whether the list is sorted under it: O(k! · total characters) for k letters.

The key idea

Sorted order is a chain of pairwise comparisons, so all the information sits in adjacent pairs of words. For a pair, find the first position where they differ: if the letters there are a and b, then a must come before b in the alphabet. Later positions carry no information, because the comparison was already decided. If there is no differing position, one word is a prefix of the other; that is fine when the shorter comes first and impossible otherwise, so the answer is "".

Each rule becomes a directed edge a → b in a graph whose nodes are all letters that appear anywhere (including letters that end up with no rules at all). An alphabet consistent with every rule is exactly a topological order of this graph.

Kahn's algorithm builds one: count incoming edges, start with letters that have none, and repeatedly output a letter and remove its outgoing edges, which may free up new letters. If some letters are never output, every one of them still has a predecessor waiting, which only happens on a cycle such as x < y and y < x. In that case no alphabet exists and we return "".

Comparing adjacent pairs touches each character at most twice, and the graph has at most 26 nodes.

Complexity

• Time: O(C), where C is the total number of characters (the graph has at most 26 letters)
• Space: O(1) beyond the input (at most 26 letters and 26² edges)

Python

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Every letter that appears is a node; edge a -> b means "a comes before b".
        after = {ch: set() for word in words for ch in word}
        indegree = {ch: 0 for ch in after}

        # Only adjacent words carry information, and only at their first difference.
        for first, second in zip(words, words[1:]):
            for a, b in zip(first, second):
                if a != b:
                    if b not in after[a]:
                        after[a].add(b)
                        indegree[b] += 1
                    break
            else:
                # No difference found: one word is a prefix of the other,
                # so the longer one must not come first.
                if len(first) > len(second):
                    return ""

        # Kahn's algorithm: repeatedly output a letter with no remaining predecessors.
        queue = deque(ch for ch in after if indegree[ch] == 0)
        order = []
        while queue:
            ch = queue.popleft()
            order.append(ch)
            for nxt in after[ch]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        # Letters that never reached indegree 0 sit on a cycle.
        return "".join(order) if len(order) == len(after) else ""

JavaScript

var alienOrder = function(words) {
  // Every letter that appears is a node; edge a -> b means "a comes before b".
  const after = new Map();
  const indegree = new Map();
  for (const word of words) {
    for (const ch of word) {
      if (!after.has(ch)) {
        after.set(ch, new Set());
        indegree.set(ch, 0);
      }
    }
  }

  // Only adjacent words carry information, and only at their first difference.
  for (let i = 0; i + 1 < words.length; i++) {
    const first = words[i], second = words[i + 1];
    const shared = Math.min(first.length, second.length);
    let j = 0;
    while (j < shared && first[j] === second[j]) j++;
    if (j === shared) {
      // One word is a prefix of the other, so the longer one must not come first.
      if (first.length > second.length) return "";
      continue;
    }
    const a = first[j], b = second[j];
    if (!after.get(a).has(b)) {
      after.get(a).add(b);
      indegree.set(b, indegree.get(b) + 1);
    }
  }

  // Kahn's algorithm: repeatedly output a letter with no remaining predecessors.
  const queue = [...after.keys()].filter(ch => indegree.get(ch) === 0);
  const order = [];
  while (queue.length) {
    const ch = queue.shift();
    order.push(ch);
    for (const nxt of after.get(ch)) {
      indegree.set(nxt, indegree.get(nxt) - 1);
      if (indegree.get(nxt) === 0) queue.push(nxt);
    }
  }

  // Letters that never reached indegree 0 sit on a cycle.
  return order.length === after.size ? order.join("") : "";
};

What the interviewer is checking

This tests whether you can turn a word puzzle into a graph (extracting exactly the right edges) and then apply topological sorting, including detecting the two kinds of contradiction.

Mistakes to avoid

• Adding edges for every differing position, not just the first one in each adjacent pair.
• Missing the prefix rule: ["abc", "ab"] is invalid, not unconstrained.
• Leaving out letters that appear in words but are involved in no rule.
• Counting the same edge twice in the indegree when two pairs give the same rule.

Follow-ups to expect

• Return the order only if it is unique. (Queue must never hold two letters.)
• Return all valid alphabets. (Backtracking over zero-indegree choices.)
• Check whether a word list is sorted under a given alphabet. (Compare adjacent pairs with a rank map.)

In real software

Inferring an ordering from pairwise evidence is how build tools and package managers order dependencies, and how databases infer collation or merge partial orders from logs, always with cycle detection to reject contradictions.

Practice next