Alien Dictionary

Two neighboring words can hide one sharp clue. If "mira" appears before "miso", their shared "mi" tells you nothing; the first mismatch tells you r must come before s. Every character after that mismatch is irrelevant to this comparison.

The reusable pattern is: build a letter-precedence graph — a directed graph where an edge a → b means a must appear before b — from adjacent word pairs, then produce a topological sort, an ordering that respects every edge. The optimal traversal below is Kahn's algorithm.

Before either traversal, build the same graph:

1. Add every appearing letter as a node, including letters with no edges.
2. Compare each adjacent pair and add one edge from its first differing characters.
3. If there is no difference and the earlier word is longer, return "".
4. Store neighbors in sets. Repeating an edge must not create a second incoming edge.

Let C be the total number of characters, k the number of letters, and e the number of distinct precedence edges.

DFS topological sort — finish on the way back

Depth-first search (DFS) follows one chain of edges as far as it can before returning. Mark a letter visiting when its search starts and done when it ends. Reaching a visiting letter again proves that the clues contain a cycle.

Append each letter only after all letters that follow it are done. That creates the order backwards, so reverse it once at the end.

def alien_order(words: list[str]) -> str:
    graph: dict[str, set[str]] = {
        letter: set()
        for word in words
        for letter in word
    }
 
    for before, after in zip(words, words[1:]):
        limit = min(len(before), len(after))
        index = 0
        while index < limit and before[index] == after[index]:
            index += 1
 
        if index == limit:
            if len(before) > len(after):
                return ""
            continue
 
        graph[before[index]].add(after[index])
 
    state = {letter: 0 for letter in graph}  # 0=new, 1=visiting, 2=done
    reverse_order: list[str] = []
 
    def visit(letter: str) -> bool:
        if state[letter] == 1:
            return False
        if state[letter] == 2:
            return True
 
        state[letter] = 1
        for next_letter in graph[letter]:
            if not visit(next_letter):
                return False
        state[letter] = 2
        reverse_order.append(letter)
        return True
 
    for letter in graph:
        if not visit(letter):
            return ""
 
    reverse_order.reverse()
    return "".join(reverse_order)

Time O(C), space O(k + e) — every adjacent comparison, node, and distinct edge is processed once. The recursion stack holds at most k letters.

Kahn's topological sort — remove ready letters

Kahn's algorithm tracks each node's indegree, the number of edges pointing into it. A zero-indegree letter has no unmet requirement, so it can safely be placed next. Keep ready letters in a queue, a first-in, first-out line. Remove a chosen letter's outgoing edges; that may make more letters ready.

from collections import deque
 
 
def alien_order(words: list[str]) -> str:
    graph: dict[str, set[str]] = {
        letter: set()
        for word in words
        for letter in word
    }
    indegree = {letter: 0 for letter in graph}
 
    for before, after in zip(words, words[1:]):
        limit = min(len(before), len(after))
        index = 0
        while index < limit and before[index] == after[index]:
            index += 1
 
        if index == limit:
            if len(before) > len(after):
                return ""
            continue
 
        earlier = before[index]
        later = after[index]
        if later not in graph[earlier]:
            graph[earlier].add(later)
            indegree[later] += 1
 
    ready = deque(
        letter
        for letter in graph
        if indegree[letter] == 0
    )
    order: list[str] = []
 
    while ready:
        letter = ready.popleft()
        order.append(letter)
 
        for next_letter in graph[letter]:
            indegree[next_letter] -= 1
            if indegree[next_letter] == 0:
                ready.append(next_letter)
 
    if len(order) != len(graph):
        return ""
    return "".join(order)

Every letter you append has no remaining predecessor, so appending it can't violate an edge. If the queue empties before all k letters are placed, every remaining letter is trapped behind another remaining letter; following those requirements eventually closes a cycle.

Time O(C), space O(k + e) — graph construction reads the input once, and Kahn's traversal removes each node and edge once.

Every valid input here has one forced order, so Kahn's queue never presents a real tie. The durable move is the pattern itself: adjacent first differences become graph edges, and topological sorting turns those local clues into one global order.