Alien Dictionary (LC 269)

Pattern: Topological sort on implicit graph + cycle detection
Difficulty: Hard (Premium; Blind 75 graph favorite)
Key Concept: Compare adjacent words to extract ordered letter edges; a valid alphabet is a topological order of that graph — impossible if there is a cycle or a prefix violation (longer word before shorter prefix).

Problem Statement

There is a new alien language using English letters, but unknown order. You are given a list of words from the alien dictionary, sorted lexicographically by the rules of that language.

Derive any valid order of letters. If no valid order exists, return "".

Input: String[] words
Output: String — permutation of distinct letters used, or empty.

Invalid signals:

• Prefix rule: "abc" before "ab" is invalid (sorted list would put shorter prefix first if it were a prefix).
• Cycle in inferred edges: a < b and b < a chain.

---

1. Algorithm & Pseudocode

Brute force

Generate every permutation of distinct letters; for each permutation, check if all adjacent word pairs are sorted — O(k! · n) — astronomical.

Optimal

1. Build adjacency: for i from 0 to len(words)-2:
     compare words[i] and words[i+1] char by char
     first differing position c1, c2 gives edge c1 -> c2; break inner loop
     if words[i+1] is strict prefix of words[i]: return ""

2. Collect all nodes (letters appearing in words)

3. Kahn (indegree) or DFS post-order topo sort with cycle detection

4. If processed nodes < total nodes: cycle -> return ""
   else return topo order as string

DFS post-order (reverse of finishing order):

 visiting, visited flags per node
 dfs(u):
   if u in visiting: cycle
   if u in visited: return
   mark visiting u
   for v in adj[u]: dfs(v)
   unmark visiting, mark visited
   append u to result (front or reverse at end)

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Only adjacent sorted words give reliable constraints; non-adjacent pairs are transitively implied.
• First mismatch between w1 and w2 tells you w1[k] < w2[k] in alien order; later characters in those words are unconstrained by that pair.
• Topological sort works only on DAGs; a cycle means contradictory ordering.
• Empty dictionary / single letter: still valid — return that letter.

---

3. The Dry Run

words = ["wrt","wrf","er","ett","rftt"]

Compare	First diff	Edge
wrt vs wrf	index 2: t vs f	t → f
wrf vs er	index 0: w vs e	w → e
er vs ett	index 1: r vs t	r → t
ett vs rftt	index 0: e vs r	e → r

Graph edges: t→f, w→e, r→t, e→r → chain w → e → r → t → f.

Kahn indegrees: w:0, e:1, r:1, t:1, f:1 → one valid order wertf (others possible if parallel branches).

Invalid prefix: ["abc","ab"] → on compare, all chars match and second word shorter → return "".

---

4. Java Solution

Brute Force

Omitted in production; conceptually permutation check — not suitable for constraints.

Optimal

Kahn’s algorithm

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indeg = new HashMap<>();

        for (String w : words) {
            for (char c : w.toCharArray()) {
                adj.putIfAbsent(c, new HashSet<>());
                indeg.putIfAbsent(c, 0);
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String a = words[i], b = words[i + 1];
            int len = Math.min(a.length(), b.length());
            int j = 0;
            while (j < len && a.charAt(j) == b.charAt(j)) j++;
            if (j == len && a.length() > b.length()) return "";
            if (j < len) {
                char u = a.charAt(j), v = b.charAt(j);
                if (adj.get(u).add(v)) {
                    indeg.put(v, indeg.get(v) + 1);
                }
            }
        }

        ArrayDeque<Character> q = new ArrayDeque<>();
        for (char c : indeg.keySet()) {
            if (indeg.get(c) == 0) q.add(c);
        }

        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            char u = q.poll();
            sb.append(u);
            for (char v : adj.get(u)) {
                indeg.put(v, indeg.get(v) - 1);
                if (indeg.get(v) == 0) q.add(v);
            }
        }

        return sb.length() == indeg.size() ? sb.toString() : "";
    }
}

DFS + cycle detection

import java.util.*;

class SolutionDFS {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        for (String w : words) {
            for (char c : w.toCharArray()) adj.putIfAbsent(c, new HashSet<>());
        }
        for (int i = 0; i < words.length - 1; i++) {
            String a = words[i], b = words[i + 1];
            int j = 0, len = Math.min(a.length(), b.length());
            while (j < len && a.charAt(j) == b.charAt(j)) j++;
            if (j == len && a.length() > b.length()) return "";
            if (j < len) adj.get(a.charAt(j)).add(b.charAt(j));
        }

        Map<Character, Integer> state = new HashMap<>(); // 0=unseen,1=visiting,2=done
        for (char c : adj.keySet()) state.put(c, 0);

        Deque<Character> stack = new ArrayDeque<>();
        for (char c : adj.keySet()) {
            if (state.get(c) == 0 && !dfs(c, adj, state, stack)) return "";
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.append(stack.pop());
        return sb.toString();
    }

    private boolean dfs(char u, Map<Character, Set<Character>> adj,
                        Map<Character, Integer> state, Deque<Character> stack) {
        state.put(u, 1);
        for (char v : adj.get(u)) {
            if (state.get(v) == 1) return false;
            if (state.get(v) == 0 && !dfs(v, adj, state, stack)) return false;
        }
        state.put(u, 2);
        stack.push(u);
        return true;
    }
}

Time: O(C + V + E) with C = total characters, V = unique letters (≤ 26), E ≤ comparisons.
Space: O(V + E).

---

5. The “Java vs. Others” Edge

• Map<Character, ...> — autoboxing char keys is fine at ≤ 26 letters.
• StringBuilder for output; ArrayDeque for Kahn.
• Lexicographic tie-breaking among valid topos is not required — return any valid order.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute permutations	factorial	—	Infeasible
Build graph + Kahn / DFS topo	O(N + V + E)	O(V + E)	N = total chars in all words

---

ASCII: Edges from word order

words:  ... xa...     xb...
              ^         ^
              same prefix until first mismatch

Edge:  a ---> b   (a before b in alien alphabet)

Invalid:
words[i]   = "abcde"
words[i+1]= "abc"     (shorter is full prefix of longer -> impossible)