Alien Dictionary

The problem

words is a list of words that is said to be sorted in the dictionary order of an alien language. The language uses the lowercase letters of English, but in an order you do not know. Return a string that holds every letter that appears in words exactly once, in an order that agrees with how the list is sorted. If several orders agree, return any one of them. If none can, return an empty string. In dictionary order, the first position where two words differ decides which comes first, and a word comes before any longer word that begins with it.

What to write

function solve(words: string[]): string

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

Output
"wertf"

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

Output
"zx"

Constraints

Words contain lowercase English letters.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Any order that agrees with the list is accepted, so you are not looking for one special order. A letter that no comparison says anything about can go anywhere, but it must still be in the answer. And the list may contradict itself, in which case the answer is an empty string.

2. Hint 2: Ask a smaller question

   In an English dictionary, cat comes before cow. Which two letters does that let you compare, and which letters does it tell you nothing about? Now take wrt and wrf from example 1: what is the one thing this pair tells you about the alien alphabet?

3. Hint 3: Name the pattern

   Each word and the next give at most one fact: this letter comes before that letter. Facts that say one thing must come before another are the signal for topological ordering: put the letters in a line so that every fact holds. If the facts form a cycle, a chain that leads back to its start, no order exists. Read the lesson on topological ordering.

4. Hint 4: State the invariant

   Give each letter a count: the number of letters that must come before it and are not in the order yet. A letter may be written only when its count is 0. So the order built so far never breaks a fact, and letters on a cycle never reach 0.

5. Hint 5: Sketch the pseudocode

   Every letter starts at count 0. For neighboring words: a longer word before its own beginning means an empty string; otherwise record the first differing pair once, adding 1 to the later letter. Queue letters at 0. Move each to the order and lower its followers, queueing those that reach 0. Return the order if complete, else an empty string.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

The first differing character between neighboring words defines an ordering edge. Reject reversed prefixes, then topologically sort the character graph.

The slow way

Collect the different letters and try every arrangement of them. For each arrangement, check whether the word list really is sorted under that alphabet, and return the first one that passes. It is correct, but 5 letters already have 120 arrangements, and 26 letters have a number of arrangements with 27 digits.

The insight

A sorted list hides small facts. Two neighboring words are in the right order because of the first position where they differ: the letter of the earlier word comes before the letter of the later word. Nothing else in the pair tells you anything about the alphabet. Collect these facts, and what is left is a known problem, topological ordering: line the letters up so that every fact holds.

Step by step

1. Start every letter with no followers and a count of 0. A letter's followers are the letters that a fact puts after it; its count is the number of facts that put a letter before it. Every letter gets an entry, so a letter without any fact still reaches the answer.
2. Compare each word with the word that comes right after it. If every word is in order with the next one, the whole list is sorted. So neighboring pairs hold everything the list can tell you, and comparing words that are further apart adds nothing new.
3. A word placed before its own beginning: no alphabet allows that. In any dictionary a word comes before every longer word that begins with it, whatever the alphabet. A list with abc before ab breaks that rule, so the answer is an empty string.
4. Find the first position where they differ and record that one fact. Only the first difference decides the order of two words, so the letters after it tell you nothing. The fact is recorded once: the later letter joins the earlier letter's followers and its count goes up by 1.
5. Put every letter with a count of 0 in a queue. A queue is a line: you add at the back and take from the front. A letter with count 0 has no letter that must come before it, so it may be written now.
6. Move the front letter to the order; followers that drop to 0 queue up. Once a letter is in the order, each of its followers waits for one letter fewer. A follower whose count reaches 0 has all its earlier letters written, so it may come next.
7. Return the order if it holds every letter, otherwise an empty string. Letters on a cycle, a chain of facts that leads back to its start, wait for each other and are never written. A short order therefore means the facts contradict each other, and the answer is an empty string.

The same numbered steps are the comments in each solution.

function solve(words) {
  // 1. Start every letter with no followers and a count of 0
  // A letter's followers are the letters that must come after it, and its
  // count is the number of letters that must come before it. A Set keeps its
  // items in the order they were added, so the answer is the same on every run.
  const adj = new Map(),
    degree = new Map();
  for (const word of words)
    for (const ch of word) {
      adj.set(ch, new Set());
      degree.set(ch, 0);
    }
  // 2. Compare each word with the word that comes right after it
  for (let i = 1; i < words.length; i++) {
    const a = words[i - 1],
      b = words[i];
    // 3. A word placed before its own beginning: no alphabet allows that
    if (a.length > b.length && a.startsWith(b)) return "";
    // 4. Find the first position where they differ and record that one fact
    for (let j = 0; j < Math.min(a.length, b.length); j++)
      if (a[j] !== b[j]) {
        if (!adj.get(a[j]).has(b[j])) {
          adj.get(a[j]).add(b[j]);
          degree.set(b[j], degree.get(b[j]) + 1);
        }
        break;
      }
  }
  // 5. Put every letter with a count of 0 in a queue
  const q = [...degree.keys()].filter((k) => degree.get(k) === 0);
  // 6. Move the front letter to the order; followers that drop to 0 queue up
  const order = [];
  // Removing the first item of an array is slow, so nothing is removed:
  // i is the position of the front of the queue, and push adds at the back.
  for (let i = 0; i < q.length; i++) {
    const ch = q[i];
    order.push(ch);
    for (const next of adj.get(ch)) {
      degree.set(next, degree.get(next) - 1);
      if (degree.get(next) === 0) q.push(next);
    }
  }
  // 7. Return the order if it holds every letter, otherwise an empty string
  return order.length === degree.size ? order.join("") : "";
}

function solve(words: string[]): string {
  // 1. Start every letter with no followers and a count of 0
  // A letter's followers are the letters that must come after it, and its
  // count is the number of letters that must come before it. A Set keeps its
  // items in the order they were added, so the answer is the same on every run.
  const adj = new Map<string, Set<string>>(),
    degree = new Map<string, number>();
  for (const word of words)
    for (const ch of word) {
      adj.set(ch, new Set());
      degree.set(ch, 0);
    }
  // 2. Compare each word with the word that comes right after it
  for (let i = 1; i < words.length; i++) {
    const a = words[i - 1],
      b = words[i];
    // 3. A word placed before its own beginning: no alphabet allows that
    if (a.length > b.length && a.startsWith(b)) return "";
    // 4. Find the first position where they differ and record that one fact
    for (let j = 0; j < Math.min(a.length, b.length); j++)
      if (a[j] !== b[j]) {
        if (!adj.get(a[j])!.has(b[j])) {
          adj.get(a[j])!.add(b[j]);
          degree.set(b[j], degree.get(b[j])! + 1);
        }
        break;
      }
  }
  // 5. Put every letter with a count of 0 in a queue
  const q = [...degree.keys()].filter((k) => degree.get(k) === 0);
  // 6. Move the front letter to the order; followers that drop to 0 queue up
  const order: string[] = [];
  // Removing the first item of an array is slow, so nothing is removed:
  // i is the position of the front of the queue, and push adds at the back.
  for (let i = 0; i < q.length; i++) {
    const ch = q[i];
    order.push(ch);
    for (const next of adj.get(ch)!) {
      degree.set(next, degree.get(next)! - 1);
      if (degree.get(next) === 0) q.push(next);
    }
  }
  // 7. Return the order if it holds every letter, otherwise an empty string
  return order.length === degree.size ? order.join("") : "";
}

from collections import deque


def solve(words):
    # 1. Start every letter with no followers and a count of 0
    # A letter's followers are the letters that must come after it, and its
    # count is the number of letters that must come before it.
    # Lists, not sets: a letter has at most 25 followers, and a list keeps the
    # answer the same from one run to the next.
    graph = {}
    indegree = {}
    for word in words:
        for ch in word:
            graph[ch] = []
            indegree[ch] = 0
    # 2. Compare each word with the word that comes right after it
    for first, second in zip(words, words[1:]):
        # 3. A word placed before its own beginning: no alphabet allows that
        if len(first) > len(second) and first.startswith(second):
            return ""
        # 4. Find the first position where they differ and record that one fact
        for before, after in zip(first, second):
            if before != after:
                if after not in graph[before]:
                    graph[before].append(after)
                    indegree[after] += 1
                break
    # 5. Put every letter with a count of 0 in a queue
    # A deque is a list that is fast at both ends: append adds at the back,
    # popleft takes from the front.
    queue = deque(ch for ch in indegree if indegree[ch] == 0)
    # 6. Move the front letter to the order; followers that drop to 0 queue up
    order = []
    while queue:
        ch = queue.popleft()
        order.append(ch)
        for following in graph[ch]:
            indegree[following] -= 1
            if indegree[following] == 0:
                queue.append(following)
    # 7. Return the order if it holds every letter, otherwise an empty string
    return "".join(order) if len(order) == len(indegree) else ""

Example 1, traced

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

Output
"wertf"

Why it works

A list is sorted when every word is in order with the next, and the alphabet affects a pair only at its first differing letters. So the facts are all the list says about the alphabet. A letter is written only after every letter that must come before it, so the order breaks no fact. Letters never written wait for each other in a cycle, and then no order exists.

Time and space

Time O(total characters + edges), extra space O(alphabet + edges). Setting up and comparing neighbors read each character of each word a few times: the total characters. Each recorded fact, called an edge, is followed once, when its first letter is written. The lists and counts hold one entry per letter of the alphabet and one per edge.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• The letters inside one word say nothing about the alphabet. Treating wrt as proof that w comes before r and r before t adds false facts: in example 1 they contradict the real ones, and the answer comes out empty.
• Stop at the first position where two words differ. Comparing further invents facts: for the list ab, ba the second position would say that b comes before a, against the first, and the answer would be empty instead of ab.
• A word listed before its own beginning, such as abc before ab, makes the list impossible. Without a check for that, the pair gives no fact at all, and the answer is abc instead of an empty string.

Pattern

Topological ordering. Builds on Course Schedule II.

Keep going