Alien Dictionary

Problem

An alien language uses lowercase English letters, but with its own unknown alphabet order. You’re given a list of words that is claimed to be sorted lexicographically by that alien alphabet.

Recover and return a string containing every letter that appears in words, arranged in an order consistent with the sorting. If several orders are consistent, any one is accepted. If no order can explain the given list (the claim is contradictory), return "".

Lexicographic rules are the usual ones: words are compared at the first differing position; if there is no differing position, the shorter word must come first.

Examples

• words = ["wrt","wrf","er","ett","rftt"] → "wertf" — pairs give t<f, w<e, r<t, e<r; chaining them: w, e, r, t, f.
• words = ["z","x"] → "zx" — the single comparison says z comes before x.
• words = ["z","x","z"] → "" — z<x and x<z is a contradiction (a cycle).
• words = ["abc","ab"] → "" — a longer word may not precede its own prefix in any alphabet.

Constraints

• 1 <= len(words) <= 100
• 1 <= len(words[i]) <= 100
• Only lowercase English letters, so at most 26 distinct characters.

Think about it first

TL;DR

Build precedence edges from adjacent word pairs, then Kahn’s topological sort — O(C) time (total characters), O(1) space (≤26 letters, ≤26² edges).

Approach 1 — Brute force (test every alphabet permutation)

Collect the distinct letters, then try each permutation of them as a candidate alphabet and check whether it makes the word list sorted.

from itertools import permutations

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        letters = sorted({c for w in words for c in w})

        def sorted_under(alphabet: str) -> bool:
            rank = {c: i for i, c in enumerate(alphabet)}
            for w1, w2 in zip(words, words[1:]):
                key1 = [rank[c] for c in w1]
                key2 = [rank[c] for c in w2]
                if key1 > key2:
                    return False
            return True

        for perm in permutations(letters):
            candidate = "".join(perm)
            if sorted_under(candidate):
                return candidate
        return ""

Complexity: O(L! · C) with L distinct letters and C total characters. At L = 26 that’s ~4 × 10²⁶ permutations — dead on arrival.

Approach 2 — Precedence graph + Kahn’s BFS topological sort

The insight: the word list is a set of constraints, not data to search. Each adjacent pair contributes exactly one edge: at the first differing position, first_letter → second_letter (“comes before”). Any letter order consistent with all edges is an answer — which is the definition of a topological sort of a directed graph. Kahn’s algorithm produces one: repeatedly emit a node with in-degree 0 (nothing left that must precede it) and decrement its neighbors’ in-degrees; if you finish with fewer nodes emitted than exist, the leftovers form a cycle → contradiction → "". One trap needs handling before any graph work: if two adjacent words never differ and the first is longer ("abc" before "ab"), no alphabet can fix that — return "" immediately.

from collections import deque

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        adj = {c: set() for w in words for c in w}
        indegree = {c: 0 for c in adj}

        for w1, w2 in zip(words, words[1:]):
            found = False
            for a, b in zip(w1, w2):
                if a != b:
                    if b not in adj[a]:
                        adj[a].add(b)
                        indegree[b] += 1
                    found = True
                    break
            if not found and len(w1) > len(w2):
                return ""  # longer word before its own prefix: impossible

        queue = deque(c for c in indegree if indegree[c] == 0)
        order = []
        while queue:
            c = queue.popleft()
            order.append(c)
            for nxt in adj[c]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        if len(order) < len(adj):
            return ""  # a cycle kept some letters at indegree > 0
        return "".join(order)

Walkthrough (words = ["wrt","wrf","er","ett","rftt"]):

• Pairs → edges: wrt/wrf differ at index 2 → t→f; wrf/er at index 0 → w→e; er/ett at index 1 → r→t; ett/rftt at index 0 → e→r.
• In-degrees: w:0, e:1, r:1, t:1, f:1. Queue starts as [w].
• Pop w → emit; e drops to 0, enqueue. Pop e → emit; r drops to 0. Pop r → emit; t drops to 0. Pop t → emit; f drops to 0. Pop f → emit.
• All 5 letters emitted → "wertf".

Complexity: building edges scans every adjacent pair once, O(C) total characters; the sort itself is O(V + E) ≤ O(26 + 26²). Overall O(C) time, O(1) extra space.

Approach 3 — DFS topological sort (reverse postorder)

The insight: a depth-first search finishes a node only after all its descendants are finished, so listing nodes by decreasing finish time (reverse postorder) is automatically a topological order. Cycle detection comes free from three-coloring: hitting a node that is currently in progress on the stack means a back edge → cycle.

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        adj = {c: set() for w in words for c in w}
        for w1, w2 in zip(words, words[1:]):
            min_len = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""
            for a, b in zip(w1, w2):
                if a != b:
                    adj[a].add(b)
                    break

        UNSEEN, IN_PROGRESS, DONE = 0, 1, 2
        state = {c: UNSEEN for c in adj}
        out = []

        def dfs(c: str) -> bool:
            state[c] = IN_PROGRESS
            for nxt in adj[c]:
                if state[nxt] == IN_PROGRESS:
                    return False  # back edge: cycle
                if state[nxt] == UNSEEN and not dfs(nxt):
                    return False
            state[c] = DONE
            out.append(c)  # postorder: appended after all successors
            return True

        for c in adj:
            if state[c] == UNSEEN and not dfs(c):
                return ""
        out.reverse()
        return "".join(out)

Walkthrough (words = ["z","x","z"]): edges z→x and x→z. DFS from z: mark in-progress, visit x, mark in-progress, visit z — already in progress → cycle → "".

Complexity: same as Kahn — O(C) time, O(1) space. Kahn is usually preferred in interviews because the cycle check (“emitted fewer than all”) is harder to get wrong.

Common pitfalls

• Missing the prefix rule: ["abc","ab"] yields no differing position, and the fix is returning "", not skipping the pair.
• Deriving constraints from non-adjacent pairs or from every differing position — only the first difference of each adjacent pair is a valid fact.
• Adding duplicate edges without a set, which corrupts in-degree counts and strands letters in the queue.
• Dropping letters that appear in words but in no constraint — they have in-degree 0 and must still be emitted.

Pattern takeaway

When a problem gives you ordering facts (“this must come before that”) and asks for a consistent sequence — course schedules, build dependencies, alphabet recovery — model each fact as a directed edge and topologically sort. Kahn’s in-degree queue and DFS reverse postorder are interchangeable; existence of an answer is exactly acyclicity, so the cycle check is the impossibility check.