269. Alien Dictionary (Hard)

Problem

You are given a list of strings words from an alien language, sorted lexicographically by its rules. Return a string of unique letters in order; if impossible, return "".

Example

words = ["wrt","wrf","er","ett","rftt"] → "wertf"
words = ["z","x"] → "zx"
words = ["z","x","z"] → "" (contradiction)

LeetCode 269 (premium) · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try all character orderings

For each permutation of the distinct letters, test whether the given words are lexicographically ordered under it. Return the first permutation that works.

from itertools import permutations

def alien_order(words):
    chars = set(c for w in words for c in w)
    for perm in permutations(sorted(chars)):                    # L1: K! orderings
        rank = {ch: i for i, ch in enumerate(perm)}
        valid = True
        for w1, w2 in zip(words, words[1:]):                    # L2: W-1 adjacent pairs
            cmp_done = False
            for a, b in zip(w1, w2):
                if a != b:
                    if rank[a] > rank[b]:
                        valid = False
                    cmp_done = True
                    break
            if not cmp_done and len(w1) > len(w2):              # prefix contradiction
                valid = False
            if not valid:
                break
        if valid:
            return "".join(perm)
    return ""

function alienOrder(words: string[]): string {
    const chars = new Set(words.join('').split(''));
    const charArr = Array.from(chars).sort();

    function permutations(arr: string[]): string[][] {
        if (arr.length <= 1) return [arr];
        const result: string[][] = [];
        for (let i = 0; i < arr.length; i++) {
            const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
            for (const p of permutations(rest)) result.push([arr[i], ...p]);
        }
        return result;
    }

    for (const perm of permutations(charArr)) {                 // L1: K! orderings
        const rank = new Map(perm.map((ch, i) => [ch, i]));
        let valid = true;
        for (let i = 0; i < words.length - 1 && valid; i++) {   // L2: W-1 adjacent pairs
            const [w1, w2] = [words[i], words[i + 1]];
            let cmpDone = false;
            for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
                if (w1[j] !== w2[j]) {
                    if (rank.get(w1[j])! > rank.get(w2[j])!) valid = false;
                    cmpDone = true; break;
                }
            }
            if (!cmpDone && w1.length > w2.length) valid = false;
        }
        if (valid) return perm.join('');
    }
    return '';
}

final class Solution {
    func alienOrder(_ words: [String]) -> String {
        let characters = Array(Set(words.flatMap(Array.init))).sorted()
        func isSorted(_ order: [Character]) -> Bool {
            let rank = Dictionary(uniqueKeysWithValues: order.enumerated().map { ($0.element, $0.offset) })
            for index in 0..<(words.count - 1) {
                let left = Array(words[index]), right = Array(words[index + 1])
                var decided = false
                for position in 0..<min(left.count, right.count) where left[position] != right[position] {
                    if rank[left[position]]! > rank[right[position]]! { return false }
                    decided = true; break
                }
                if !decided && left.count > right.count { return false }
            }
            return true
        }
        var answer: [Character]?
        func permute(_ remaining: [Character], _ current: [Character]) {
            if answer != nil { return }
            if remaining.isEmpty { if isSorted(current) { answer = current }; return }
            for index in remaining.indices {
                var next = remaining; let character = next.remove(at: index)
                permute(next, current + [character])
            }
        }
        permute(characters, [])
        return answer.map { String($0) } ?? ""
    }
}

Where the time goes, line by line

Variables: W = number of words, L = max word length, K = unique characters across all words (≤ 26).

Line	Per-call cost	Times executed	Contribution
L1 (generate permutations)	$O(K!)$	1	$O(K!)$
L2 (test each permutation against words)	$O(W · L)$	K!	$O(K! · W · L)$ ← dominates

Complexity

Time: $O(K! · W · L)$ , driven by L2. Infeasible past K around 8.
Space: $O(K)$ .

Educational only; don’t actually write this.

Approach 2: Build graph from adjacent-word constraints + Kahn’s BFS (canonical)

From adjacent word pairs, extract the first differing character pair — that’s a directed edge (earlier → later). Then topologically sort.

Edge cases: if a word is a strict prefix of the previous word (e.g., ["abc", "ab"]), it’s a contradiction, return "".

from collections import defaultdict, deque

def alien_order(words):
    # 1. Collect all distinct characters
    in_deg = {c: 0 for w in words for c in w}  # L1: O(W * L) to build
    graph = defaultdict(set)                     # L2: O(1)

    # 2. Build edges from adjacent pairs
    for w1, w2 in zip(words, words[1:]):         # L3: W-1 iterations
        # Prefix contradiction
        if len(w1) > len(w2) and w1.startswith(w2):  # L4: O(L) check
            return ""
        for a, b in zip(w1, w2):                 # L5: up to L char comparisons
            if a != b:
                if b not in graph[a]:
                    graph[a].add(b)
                    in_deg[b] += 1               # L6: O(1) edge insertion
                break

    # 3. Kahn's BFS
    q = deque([c for c, d in in_deg.items() if d == 0])  # L7: O(K)
    order = []
    while q:                                     # L8: K iterations total
        c = q.popleft()                          # L9: O(1)
        order.append(c)
        for nb in graph[c]:                      # L10: each edge visited once
            in_deg[nb] -= 1
            if in_deg[nb] == 0:
                q.append(nb)                     # L11: O(1)

    return "".join(order) if len(order) == len(in_deg) else ""  # L12: O(K)

function alienOrder(words: string[]): string {
    // 1. Collect all distinct characters
    const inDeg = new Map<string, number>();
    for (const w of words) for (const c of w) if (!inDeg.has(c)) inDeg.set(c, 0);  // L1
    const graph = new Map<string, Set<string>>();                                     // L2

    // 2. Build edges from adjacent pairs
    for (let i = 0; i < words.length - 1; i++) {                                     // L3: W-1 iterations
        const [w1, w2] = [words[i], words[i + 1]];
        if (w1.length > w2.length && w1.startsWith(w2)) return "";                   // L4: prefix contradiction
        for (let j = 0; j < Math.min(w1.length, w2.length); j++) {                   // L5: char comparisons
            const [a, b] = [w1[j], w2[j]];
            if (a !== b) {
                if (!graph.has(a)) graph.set(a, new Set());
                if (!graph.get(a)!.has(b)) {
                    graph.get(a)!.add(b);
                    inDeg.set(b, (inDeg.get(b) ?? 0) + 1);                            // L6: edge insertion
                }
                break;
            }
        }
    }

    // 3. Kahn's BFS
    const q: string[] = [];
    for (const [c, d] of inDeg) if (d === 0) q.push(c);                              // L7: O(K)
    const order: string[] = [];
    let head = 0;
    while (head < q.length) {                                                         // L8: K iterations
        const c = q[head++];                                                          // L9: O(1)
        order.push(c);
        for (const nb of (graph.get(c) ?? [])) {                                      // L10: each edge once
            inDeg.set(nb, inDeg.get(nb)! - 1);
            if (inDeg.get(nb) === 0) q.push(nb);                                      // L11: O(1)
        }
    }

    return order.length === inDeg.size ? order.join('') : "";                         // L12: O(K)
}

final class Solution {
    func alienOrder(_ words: [String]) -> String {
        let characters = Set(words.flatMap(Array.init))
        var graph = Dictionary(uniqueKeysWithValues: characters.map { ($0, Set<Character>()) })
        var indegree = Dictionary(uniqueKeysWithValues: characters.map { ($0, 0) })
        for index in 0..<(words.count - 1) {
            let left = Array(words[index]), right = Array(words[index + 1])
            if left.count > right.count && left.prefix(right.count) == right[...] { return "" }
            for position in 0..<min(left.count, right.count) where left[position] != right[position] {
                if graph[left[position]]!.insert(right[position]).inserted { indegree[right[position]]! += 1 }
                break
            }
        }
        var queue = indegree.filter { $0.value == 0 }.map(\.key).sorted(), result: [Character] = []
        while !queue.isEmpty {
            let current = queue.removeFirst(); result.append(current)
            for next in graph[current]!.sorted() {
                indegree[next]! -= 1
                if indegree[next] == 0 { queue.append(next); queue.sort() }
            }
        }
        return result.count == characters.count ? String(result) : ""
    }
}

Where the time goes, line by line

Variables: W = number of words, L = max word length, K = unique characters across all words (≤ 26).

Line	Per-call cost	Times executed	Contribution
L1 (build in_deg)	$O(1)$	W * L chars	$O(W * L)$
L3-L6 (edge extraction)	$O(L)$ per pair	W - 1 pairs	$O(W * L)$
L7 (seed queue)	$O(K)$	1	$O(K)$
L8-L11 (Kahn’s BFS)	$O(1)$ per node/edge	K nodes + E edges	$O(K + E)$ ← dominates on large inputs
L12 (join)	$O(K)$	1	$O(K)$

Complexity

Time: $O(W * L + K + E)$ , driven by L3-L6 and L8-L11. Since K ≤ 26, this simplifies to $O(W * L)$ in practice.
Space: $O(K + E)$ for the graph and in-degree map.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Try every permutation	$O(K! · W · L)$	$O(K)$
Kahn’s BFS	*$O(W L + K + E)$**	$O(K + E)$
DFS post-order reversed	$O(W * L + K + E)$	$O(K + E)$

Kahn’s is the canonical answer — you extract edges in one pass and topologically sort in another. The prefix-contradiction check is the easy-to-miss gotcha.

# Quick smoke tests, paste into a REPL or save as test_alien_dictionary.py and run.
# Uses the canonical implementation (Approach 2: Kahn's BFS).

from collections import defaultdict, deque

def alien_order(words):
    in_deg = {c: 0 for w in words for c in w}
    graph = defaultdict(set)

    for w1, w2 in zip(words, words[1:]):
        if len(w1) > len(w2) and w1.startswith(w2):
            return ""
        for a, b in zip(w1, w2):
            if a != b:
                if b not in graph[a]:
                    graph[a].add(b)
                    in_deg[b] += 1
                break

    q = deque([c for c, d in in_deg.items() if d == 0])
    order = []
    while q:
        c = q.popleft()
        order.append(c)
        for nb in graph[c]:
            in_deg[nb] -= 1
            if in_deg[nb] == 0:
                q.append(nb)

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

def _run_tests():
    # Canonical example: "wertf" is one valid order
    result = alien_order(["wrt", "wrf", "er", "ett", "rftt"])
    assert result == "wertf", f"got {result!r}"

    # Simple two-word case
    result = alien_order(["z", "x"])
    assert result == "zx", f"got {result!r}"

    # Contradiction: z comes both before and after itself
    assert alien_order(["z", "x", "z"]) == ""

    # Prefix contradiction: "abc" cannot come before "ab" lexicographically
    assert alien_order(["abc", "ab"]) == ""

    # Single word: any order of its unique chars is valid
    result = alien_order(["abc"])
    assert set(result) == set("abc"), f"got {result!r}"

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function alienOrder(words: string[]): string {
    const inDeg = new Map<string, number>();
    for (const w of words) for (const c of w) if (!inDeg.has(c)) inDeg.set(c, 0);
    const graph = new Map<string, Set<string>>();

    for (let i = 0; i < words.length - 1; i++) {
        const [w1, w2] = [words[i], words[i + 1]];
        if (w1.length > w2.length && w1.startsWith(w2)) return "";
        for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
            const [a, b] = [w1[j], w2[j]];
            if (a !== b) {
                if (!graph.has(a)) graph.set(a, new Set());
                if (!graph.get(a)!.has(b)) {
                    graph.get(a)!.add(b);
                    inDeg.set(b, (inDeg.get(b) ?? 0) + 1);
                }
                break;
            }
        }
    }

    const q: string[] = [];
    for (const [c, d] of inDeg) if (d === 0) q.push(c);
    const order: string[] = [];
    let head = 0;
    while (head < q.length) {
        const c = q[head++];
        order.push(c);
        for (const nb of (graph.get(c) ?? [])) {
            inDeg.set(nb, inDeg.get(nb)! - 1);
            if (inDeg.get(nb) === 0) q.push(nb);
        }
    }
    return order.length === inDeg.size ? order.join('') : "";
}

console.assert(alienOrder(["wrt","wrf","er","ett","rftt"]) === "wertf");
console.assert(alienOrder(["z","x"]) === "zx");
console.assert(alienOrder(["z","x","z"]) === "");
console.assert(alienOrder(["abc","ab"]) === "");
console.log("all tests pass");

Graphs, topological sort of a DAG built from ordering constraints
Hash Tables, adjacency map (set per node to dedup edges)

Topological Sort, the dependency order pattern for prerequisites and directed acyclic graphs.
Graph Traversal, the visited set model for exploring nodes and edges without repetition.

269. Alien Dictionary (Hard)

Problem

Try it yourself

Approach 1: Brute force, try all character orderings

Approach 2: Build graph from adjacent-word constraints + Kahn’s BFS (canonical)

Summary

Test cases

Related data structures

Related concepts