Alien Dictionary (LeetCode 269)

The problem

An alien language uses lowercase English letters in an unknown order. You get a list of words that is sorted in that alien order. Return a string of all the letters that appear, in an order consistent with the list. If the list is contradictory, return "". Any valid order is accepted.

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

“wrt” before “wrf” tells you t comes before f. “wrf” before “er” gives w before e. “er” before “ett” gives r before t. “ett” before “rftt” gives e before r. Chain them: w, e, r, t, f.

How to think about it

Start with brute force. Try every permutation of the letters and check whether the word list is sorted under it. With up to 26 letters that is 26! orders. Impossible.

The key insight: each adjacent pair of words gives at most one rule. Compare two neighbouring words letter by letter. The first position where they differ tells you the first word’s letter comes before the second’s. Everything after that position tells you nothing, because the order was already decided there. Comparing only adjacent pairs is enough, since sortedness is transitive.

Rules plus “find an order” means topological sort. Each rule x → y is a directed edge. A valid alphabet is an ordering where every edge points forward: a topological order. Kahn’s algorithm builds it. Start with letters that have no incoming edges (nothing must come before them). Output one, remove its outgoing edges, and add any letter whose in-degree drops to 0. If some letters never reach in-degree 0, there is a cycle: the rules contradict each other.

One extra trap: the prefix rule. If a word is followed by its own prefix ("abc" before "ab"), no alphabet can make that sorted. That is invalid input; return "".

Which pattern is this? Topological sort. The tell is “derive an order from pairwise before/after constraints”.

Approach

1. Give every letter that appears an in-degree of 0.
2. For each adjacent pair (a, b), find the first differing position. Add the edge a[i] → b[i] if it is new, and bump the in-degree of b[i].
3. If there is no differing position and a is longer than b, return "".
4. Queue every letter with in-degree 0. Pop one, append it to the result, and decrement its neighbours, queueing any that reach 0.
5. If the result has every letter, return it; otherwise there was a cycle, so return "".

Solution

from collections import defaultdict, deque
def alienOrder(words):
    adj = defaultdict(set); indeg = {c: 0 for w in words for c in w}
    for a, b in zip(words, words[1:]):
        for x, y in zip(a, b):
            if x != y:                                  # first difference gives one rule
                if y not in adj[x]: adj[x].add(y); indeg[y] += 1
                break
        else:
            if len(a) > len(b): return ""      # invalid: "abc" before "ab"
    q = deque([c for c in indeg if indeg[c] == 0]); res = []
    while q:
        c = q.popleft(); res.append(c)
        for nb in adj[c]:
            indeg[nb] -= 1
            if indeg[nb] == 0: q.append(nb)
    return "".join(res) if len(res) == len(indeg) else ""   # leftovers mean a cycle
# alienOrder(["wrt","wrf","er","ett","rftt"]) -> "wertf"

Dry run

The rules found are t → f, w → e, r → t, e → r, so the in-degrees are w:0, r:1, t:1, f:1, e:1.

All five letters are placed, so the answer is “wertf”.

Complexity

• Time: O(C). C is the total number of characters across all words. Building in-degrees and comparing adjacent pairs touches each character a constant number of times. The graph has at most 26 nodes and 26² edges, so the sort itself is O(1) in alphabet terms.
• Space: O(1) for the graph (bounded by the alphabet), plus the O(26) result.

Edge cases and pitfalls

• One word returns its distinct letters in any order; there are no rules.
• Prefix trap: ["abc", "ab"] must return "". Forgetting this check is the most common bug.
• A cycle like ["a", "b", "a"] gives a → b and b → a; Kahn’s stops early and returns "".
• Letters with no rules still have to appear in the output, which is why indeg is built from every letter.
• Duplicate edges must not double-count in-degrees; the set check handles that.

Related problems

• Course Schedule II (LeetCode 210): Kahn’s algorithm on explicit prerequisites.
• Course Schedule (LeetCode 207): just detect whether a cycle exists.
• Reconstruct Itinerary (LeetCode 332): another ordering problem on a directed graph, solved with Hierholzer’s algorithm.