Alien Dictionary

Where C is the total number of characters across all words (bounded by 100 × 100 = 10^4 here, and by 26 possible letters/edges once graphs are built — more on that below).

1. Initialize a node (and in-degree 0) for every distinct letter appearing in words.
2. For each adjacent pair of words, find the first differing character position. If none exists and the first word is longer, the order is invalid (""). Otherwise add a directed edge first-diff-letter-of-w1 → first-diff-letter-of-w2 — but only if that edge hasn’t been added before (to avoid double-counting in-degree).
3. Run Kahn’s algorithm: repeatedly pop nodes with in-degree 0, append to the result, and decrement in-degree of their neighbors.
4. If the result doesn’t include every letter, there was a cycle — return "".

from collections import deque

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

        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 ""  # "abc" before "ab" is impossible in any order
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    if c2 not in adj[c1]:
                        adj[c1].add(c2)
                        indegree[c2] += 1
                    break

        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)

        return "".join(order) if len(order) == len(indegree) else ""

Worked example — words = ["wrt","wrf","er","ett","rftt"].

The four comparisons yield these edges: wrt/wrf → t → f, wrf/er → w → e, er/ett → r → t, ett/rftt → e → r — a single chain w → e → r → t → f, so the only valid order is forced.

Watch two things in the trace: how each edge is born — the comparison panel scans a pair left to right, dims the matching prefix, and stops at the first difference (amber), which is read straight off as an edge; and how Kahn consumes the graph — each scheduled letter drops a neighbor’s in-degree badge to 0, and that neighbor slides into the ready queue.

All 5 letters are scheduled on the final step, which means no cycle — so "wertf" is returned, matching the expected output.

Why it’s correct: this is standard topological sort correctness — a directed edge u → v means u must precede v in any valid ordering, and Kahn’s algorithm produces a valid linearization respecting all such constraints whenever one exists (equivalently, whenever the graph is a DAG). If some letters are never popped (in-degree never reaches 0), the remaining subgraph has a cycle, which is a direct contradiction in the alphabet’s ordering.

Complexity: let C be the total length of all words. Scanning adjacent word pairs to build edges is O(C) (each pair’s comparison is bounded by the shorter word’s length). Because there are at most 26 letters, the graph has at most 26 nodes and 26 × 25 possible edges — a constant — so the BFS itself is O(1) in terms of the alphabet, and the dominant cost is the O(C) edge-extraction pass. Space is O(1) for the graph (bounded by the fixed alphabet size) plus O(C) implicitly for reading the input.

The same edge set can be linearized with DFS instead of Kahn’s BFS: run DFS from every unvisited letter, and on the way back up the call stack (post-order), append the letter to the result. Reversing that post-order list gives a valid topological order — the same idea used in Reconstruct Itinerary’s Hierholzer traversal, and in Course Schedule II. Cycles are detected with a three-color scheme: WHITE (unvisited), GRAY (on the current DFS stack), BLACK (fully processed) — revisiting a GRAY node means a back-edge, i.e. a cycle.

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

        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 c1, c2 in zip(w1, w2):
                if c1 != c2:
                    adj[c1].add(c2)
                    break

        WHITE, GRAY, BLACK = 0, 1, 2
        color = {c: WHITE for c in adj}
        order = []

        def dfs(c: str) -> bool:
            color[c] = GRAY
            for nxt in adj[c]:
                if color[nxt] == GRAY:
                    return False  # cycle: back-edge to a node on the current path
                if color[nxt] == WHITE and not dfs(nxt):
                    return False
            color[c] = BLACK
            order.append(c)
            return True

        for c in adj:
            if color[c] == WHITE and not dfs(c):
                return ""

        return "".join(reversed(order))

Why post-order-then-reverse works: a letter is only appended to order after all letters reachable from it have already been appended. So in the final list, every letter appears before anything it points to only once reversed — i.e. reversing puts each u before its dependents v for every edge u → v, exactly the topological property required.

Complexity: identical to the BFS version — O(C) time to build the edges (bounded alphabet-size DFS afterward), O(1) / O(26) graph space. This variant is a matter of taste (iterative BFS vs. recursive DFS); Kahn’s is often preferred in interviews since it avoids recursion depth concerns, though with only 26 possible nodes here that’s not a real risk.