Alien Dictionary

HardTopological Sort · Graph🧩 Topological Sort LeetCode #269 ↗Updated Oct 30, 2026

Problem

An alien language uses lowercase English letters in an unknown order. You get a list words that is claimed to be sorted lexicographically by that alien order. Return any string containing every letter that appears in the words exactly once, arranged in an order consistent with the list. If no order can make the list sorted, return "".

Inputwords = ["wrt","wrf","er","ett","rftt"]Output"wertf"

Inputwords = ["z","x"]Output"zx"

Inputwords = ["z","x","z"]Output"" (z before x and x before z)

1 ≤ words.length ≤ 100 · 1 ≤ words[i].length ≤ 100 · lowercase letters only · any valid order is accepted

Try it yourself

Java

class Solution {
    public String alienOrder(String[] words) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Only the first differing letter of two neighbouring words tells you anything: it is a directed edge a → b. The answer is a topological order of that letter graph; a cycle, or a longer word placed before its own prefix, means "".

PatternTopological Sort

Instinct Tasks with prerequisites, "X must come before Y", or an order hidden in comparisons: build a directed graph and peel off nodes with zero in-degree.

Memory hack No prereqs? Off you go. Each finished task frees its followers; if someone is never freed, there is a cycle.

Open the Topological Sort guide →

Approaches

Brute ForceAll-Pairs Rules + Repeated Scans

Time O(N²·L + U³)Space O(U²)

Compare every pair i < j of words to collect “a before b” rules (rejecting a word that comes before its own proper prefix). Then repeatedly scan the remaining letters for one that no remaining letter must precede, append it and repeat; if none exists, there is a cycle. U ≤ 26 distinct letters, L = word length.

Java

public String alienOrder(String[] words) {
    boolean[] present = new boolean[26];
    for (String w : words) for (char ch : w.toCharArray()) present[ch - 'a'] = true;
    boolean[][] before = new boolean[26][26];       // before[a][b]: a precedes b
    for (int i = 0; i < words.length; i++) {
        for (int j = i + 1; j < words.length; j++) {
            if (!addRule(words[i], words[j], before)) return "";
        }
    }
    int total = 0;
    for (boolean p : present) if (p) total++;
    boolean[] placed = new boolean[26];
    StringBuilder order = new StringBuilder();
    while (order.length() < total) {
        int pick = -1;
        for (int c = 0; c < 26 && pick == -1; c++) {
            if (!present[c] || placed[c]) continue;
            boolean free = true;
            for (int p = 0; p < 26 && free; p++) {
                if (present[p] && !placed[p] && before[p][c]) free = false;
            }
            if (free) pick = c;
        }
        if (pick == -1) return "";                  // everyone waits on someone: cycle
        placed[pick] = true;
        order.append((char) ('a' + pick));
    }
    return order.toString();
}

// Records the first differing letter; false if b is a proper prefix of a.
private boolean addRule(String a, String b, boolean[][] before) {
    int len = Math.min(a.length(), b.length());
    for (int i = 0; i < len; i++) {
        if (a.charAt(i) != b.charAt(i)) {
            before[a.charAt(i) - 'a'][b.charAt(i) - 'a'] = true;
            return true;
        }
    }
    return a.length() <= b.length();
}

Correct, but quadratic in words and re-scans the whole rule matrix per letter.

BetterAdjacent-Pairs Rules + Repeated Scans

Time O(C + U³)Space O(U²)

Sortedness is transitive, so comparing only neighbouring words already yields every rule needed (C = total characters). The letter-peeling phase is unchanged: repeatedly pick any unplaced letter with no unplaced predecessor.

Java

public String alienOrder(String[] words) {
    boolean[] present = new boolean[26];
    for (String w : words) for (char ch : w.toCharArray()) present[ch - 'a'] = true;
    boolean[][] before = new boolean[26][26];
    for (int i = 0; i + 1 < words.length; i++) {
        String a = words[i], b = words[i + 1];
        int len = Math.min(a.length(), b.length()), j = 0;
        while (j < len && a.charAt(j) == b.charAt(j)) j++;
        if (j < len) before[a.charAt(j) - 'a'][b.charAt(j) - 'a'] = true;
        else if (a.length() > b.length()) return "";    // "abc" before "ab"
    }
    int total = 0;
    for (boolean p : present) if (p) total++;
    boolean[] placed = new boolean[26];
    StringBuilder order = new StringBuilder();
    while (order.length() < total) {
        int pick = -1;
        for (int c = 0; c < 26 && pick == -1; c++) {
            if (!present[c] || placed[c]) continue;
            boolean free = true;
            for (int p = 0; p < 26 && free; p++) {
                if (present[p] && !placed[p] && before[p][c]) free = false;
            }
            if (free) pick = c;
        }
        if (pick == -1) return "";
        placed[pick] = true;
        order.append((char) ('a' + pick));
    }
    return order.toString();
}

Rule extraction is now linear; the peel still costs O(U) per check.

OptimalAdjacent Pairs + Kahn’s BFS

Time O(C + U + E)Space O(U + E)

Store each rule once as an adjacency-list edge and track in-degrees. Start a queue with every letter of in-degree 0; popping a letter “places” it and lowers its successors’ in-degrees. If fewer than U letters get placed, the leftovers form a cycle. E ≤ min(N, U²) distinct edges.

Java

public String alienOrder(String[] words) {
    int[] indegree = new int[26];
    Arrays.fill(indegree, -1);                      // -1 = letter never used
    for (String w : words) for (char ch : w.toCharArray()) indegree[ch - 'a'] = 0;
    List<List<Integer>> next = new ArrayList<>();
    for (int i = 0; i < 26; i++) next.add(new ArrayList<>());
    boolean[][] hasEdge = new boolean[26][26];
    for (int i = 0; i + 1 < words.length; i++) {
        String a = words[i], b = words[i + 1];
        int len = Math.min(a.length(), b.length()), j = 0;
        while (j < len && a.charAt(j) == b.charAt(j)) j++;
        if (j == len) {
            if (a.length() > b.length()) return "";    // longer word before its prefix
            continue;
        }
        int u = a.charAt(j) - 'a', v = b.charAt(j) - 'a';
        if (!hasEdge[u][v]) {
            hasEdge[u][v] = true;
            next.get(u).add(v);
            indegree[v]++;
        }
    }
    Deque<Integer> queue = new ArrayDeque<>();
    int letters = 0;
    for (int c = 0; c < 26; c++) {
        if (indegree[c] >= 0) letters++;
        if (indegree[c] == 0) queue.offer(c);
    }
    StringBuilder order = new StringBuilder();
    while (!queue.isEmpty()) {
        int c = queue.poll();
        order.append((char) ('a' + c));
        for (int v : next.get(c)) {
            if (--indegree[v] == 0) queue.offer(v);
        }
    }
    return order.length() == letters ? order.toString() : "";
}

Every character and edge is touched a constant number of times — linear.

Pro tip

A DFS post-order with three colours works equally well; Kahn’s version makes cycle detection a simple count check.

At a glance

Level	Approach	Time	Space
Brute Force	All-Pairs Rules + Repeated Scans	`O(N²·L + U³)`	`O(U²)`
Better	Adjacent-Pairs Rules + Repeated Scans	`O(C + U³)`	`O(U²)`
Optimal	Adjacent Pairs + Kahn’s BFS	`O(C + U + E)`	`O(U + E)`

Common pitfalls

Missing the prefix case: ["abc","ab"] is invalid even though no letters differ.
Adding rules from letters after the first difference — they carry no information.
Dropping letters with no edges — every letter that appears must be in the output.

Interview tips

Clarify: any valid order is fine, and return "" when impossible.
Explain why adjacent pairs suffice: a sorted list is transitively ordered.
Count duplicate edges once (or tolerate them consistently) to keep in-degrees right.

Pattern

Topological sort → derive an ordering from pairwise “comes before” constraints and detect contradictions.

My notes saved in this browser