DSA Alien Dictionary

The problem

A list of foreign words arrives already sorted by an unknown letter order. The task recovers a letter order that explains the sorting. Every letter appearing in the words appears once in the answer.

Some lists admit no order at all. The answer then reports impossibility, with a reason. A valid list can allow several orders, and any one of them is a correct answer.

cases = [
    (["wrt", "wrf", "er", "ett", "rftt"], "wertf"),
    (["baa", "abcd", "abca", "cab", "cad"], "bdac"),
    (["z", "x", "z"], "impossible: cycle"),
    (["abc", "ab"], "impossible: prefix"),
]
for words, expected in cases:
    print("words:", words, "expected:", expected)

The first two lists carry enough facts to pin one order down. The third forces a letter both before and after another. The fourth places a word before its own shorter prefix.

Intuition: one pair, one fact

Compare two neighbouring words letter by letter. Their first differing letters give one fact, an ordering between those two letters. Letters after that difference carry no fact at all, because the difference already decided the pair.

Reading facts from later positions is the trap. It invents orderings the sorted list never stated. The invented facts can even contradict the real ones.

a, b = "abca", "abzx"
first = None
all_facts = []
for x, y in zip(a, b):
    if x != y:
        all_facts.append((x, y))
        if first is None:
            first = (x, y)
print("the pair's one real fact:", first[0], "before", first[1])
print("facts from every differing position:", all_facts)

Only c before z comes from this pair. The extra fact, a before x, is invented. Building a graph from invented facts can order letters wrongly, or declare a good dictionary impossible.

Brute force: try every letter order

The brute force lists every ordering of the distinct letters. It tests each ordering against every neighbouring word pair. The first ordering that explains all pairs wins.

An ordering explains a pair when the pair's first differing letters appear in that order. A pair where a word precedes its own prefix fails every ordering at once.

from itertools import permutations

def explains(order, words):
    rank = {ch: i for i, ch in enumerate(order)}
    for a, b in zip(words, words[1:]):
        if len(a) > len(b) and a.startswith(b):
            return False
        for x, y in zip(a, b):
            if x != y:
                if rank[x] > rank[y]:
                    return False
                break
    return True

words = ["wrt", "wrf", "er"]
letters = sorted({ch for w in words for ch in w})
checked = 0
found = None
for perm in permutations(letters):
    checked += 1
    if explains("".join(perm), words):
        found = "".join(perm)
        break
print("letters:", letters)
print("orders checked until a valid one:", checked)
print("a valid order:", found, "(any valid order is a correct answer)")

Five letters already mean 120 orderings in the worst case. Each extra letter multiplies the count by the new letter total. The factorial wall arrives fast, and the graph method in the next section walks around it.

The optimal solution: facts become edges, Kahn emits the order

A fact that x comes before y becomes a directed edge from x to y in a graph whose nodes are the letters. A topological order of that graph, an ordering where every edge points forward, is exactly a letter order explaining the list.

Kahn's method builds such an order directly. It repeatedly emits a letter with no incoming edges left, then removes that letter's edges. Letters that never become free must sit on a directed cycle, which means no order exists.

Ready letters stay in sorted order in this article's code. Letters are also collected into a sorted list before anything runs. Both choices make the printed answer identical on every run.

def alien_order(words):
    letters = sorted({ch for w in words for ch in w})
    after = {ch: [] for ch in letters}
    indeg = {ch: 0 for ch in letters}
    for a, b in zip(words, words[1:]):
        if len(a) > len(b) and a.startswith(b):
            return None, "prefix", 0
        for x, y in zip(a, b):
            if x != y:
                if y not in after[x]:
                    after[x].append(y)
                    indeg[y] += 1
                break
    edges = sum(len(v) for v in after.values())
    ready = sorted(ch for ch in letters if indeg[ch] == 0)
    order = []
    while ready:
        ch = ready.pop(0)
        order.append(ch)
        for nxt in sorted(after[ch]):
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                ready.append(nxt)
        ready.sort()
    if len(order) != len(letters):
        return None, "cycle", edges
    return "".join(order), "ok", edges

cases = [
    ["wrt", "wrf", "er", "ett", "rftt"],
    ["baa", "abcd", "abca", "cab", "cad"],
    ["z", "x", "z"],
    ["abc", "ab"],
]
for words in cases:
    order, why, edges = alien_order(words)
    print("words:", words, "-> order:", order, "result:", why, "edges:", edges)

Both good lists resolve to the expected orders. The cyclic list emits too few letters, so the method reports a cycle. The prefix list fails while its pairs are read, because no graph can repair that pair.

Walkthrough: building and draining the first dictionary

The walk first prints the edges the word pairs produce. It then prints the incoming-edge count of every letter, in sorted letter order. Each emission step removes one letter and lowers the counts of its successors.

words = ["wrt", "wrf", "er", "ett", "rftt"]
letters = sorted({ch for w in words for ch in w})
after = {ch: [] for ch in letters}
indeg = {ch: 0 for ch in letters}
for a, b in zip(words, words[1:]):
    for x, y in zip(a, b):
        if x != y:
            if y not in after[x]:
                after[x].append(y)
                indeg[y] += 1
            break
edges = sorted((x, y) for x in after for y in after[x])
print("edges:", edges)
print("indegrees:", [(ch, indeg[ch]) for ch in letters])
ready = sorted(ch for ch in letters if indeg[ch] == 0)
order = []
while ready:
    ch = ready.pop(0)
    order.append(ch)
    for nxt in sorted(after[ch]):
        indeg[nxt] -= 1
        if indeg[nxt] == 0:
            ready.append(nxt)
    ready.sort()
    print("emit", ch, "-> order so far:", "".join(order),
          "indegrees left:", [(c, indeg[c]) for c in letters if c not in order])
print("final order:", "".join(order))

Only w starts with no incoming edges, so it emits first. Each emission frees exactly the next letter in this dictionary. The final string reads straight off the emission order.

Complexity

Kahn's method touches each letter and each edge a constant number of times, so its time is O(letters plus edges). Its graph stores one entry per letter and per edge, so its space is also O(letters plus edges).

The brute force pays the factorial of the letter count in orderings. Each ordering also costs a pass over the word pairs, which makes the true bill worse than the counts below.

import math
for letters in [4, 5, 6, 8]:
    print("letters", letters, "- orders to try up to:", math.factorial(letters),
          " graph steps for a chain:", letters + (letters - 1))

Eight letters already mean 40320 orderings. The graph method pays 15 steps for the same letters in a chain. Counting steps, not seconds, shows why the factorial route dies early.

Edge cases and pitfalls

The prefix case deserves its own check, because it fails silently in careless code. Code that only reads first differences finds no difference in the pair abc and ab. It then reports an order for a dictionary that cannot exist.

Identical neighbouring words give no fact and break nothing. A single word gives no facts either, so every ordering of its letters is valid, and this article's code answers with its deterministic sorted-ready order.

def alien_order(words):
    letters = sorted({ch for w in words for ch in w})
    after = {ch: [] for ch in letters}
    indeg = {ch: 0 for ch in letters}
    for a, b in zip(words, words[1:]):
        if len(a) > len(b) and a.startswith(b):
            return None, "prefix", 0
        for x, y in zip(a, b):
            if x != y:
                if y not in after[x]:
                    after[x].append(y)
                    indeg[y] += 1
                break
    edges = sum(len(v) for v in after.values())
    ready = sorted(ch for ch in letters if indeg[ch] == 0)
    order = []
    while ready:
        ch = ready.pop(0)
        order.append(ch)
        for nxt in sorted(after[ch]):
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                ready.append(nxt)
        ready.sort()
    if len(order) != len(letters):
        return None, "cycle", edges
    return "".join(order), "ok", edges

print("single word:", alien_order(["hello"]))
print("identical neighbours:", alien_order(["ab", "ab", "ac"]))
print("empty word list:", alien_order([]))
print("prefix pair:", alien_order(["abc", "ab"]))
print("two-letter cycle:", alien_order(["a", "b", "a"]))

Each verdict matches its rule. The single word still lists every distinct letter once, with l appearing once although the word holds it twice. The empty list yields an empty order and no complaint.