Alien Dictionary LeetCode 269 Guide

LeetCode 269 Alien Dictionary gives you a list of strings sorted lexicographically according to some alien language's character ordering. Your task is to deduce the order of characters in that alien alphabet and return them as a string. If the ordering is ambiguous (multiple valid orderings exist), return any valid one. If the input is fundamentally invalid — meaning no consistent ordering exists — return an empty string.

The key insight is that a sorted word list implicitly encodes character ordering: when two adjacent words differ at some position, the character from the first word comes before the character from the second word in the alien alphabet. By collecting all such constraints and running topological sort on the resulting directed graph, you can recover the character order.

There are two important invalidity conditions. First, if the graph contains a cycle — meaning the ordering constraints contradict each other — no valid alphabet order exists. Second, if a shorter word appears after a longer word that is a prefix of it (for example "abc" appearing after "abcd" in the sorted list), the input violates the lexicographic sorting invariant and is also invalid.

To find ordering edges, iterate through every consecutive pair of words in the input list. For each pair, scan character by character until you find the first position where the two words differ. That difference gives you exactly one ordering constraint: the character from the first word comes before the character from the second word. Add a directed edge from that character to the other and stop scanning this pair — only the first differing character is informative.

The prefix invalidity check happens during this same scan. If you reach the end of the second word before finding a difference, and the first word is longer than the second, then the first word would sort after the second under any consistent ordering — a contradiction. This means the input is invalid and you should immediately return an empty string without further processing.

After processing all adjacent pairs, you have a complete set of ordering edges. Every unique character that appears anywhere in the words list is a node in the graph, even if it has no edges. Characters with no incoming or outgoing constraints can appear anywhere in a valid topological order — they just need to be included in the result.

Represent the graph as an adjacency list mapping each character to its set of successors, plus an in-degree map counting how many edges point into each character node. Both structures must include every unique character from the words list, even those with no ordering constraints, so they appear in the final result.

Use a set for each character's neighbors in the adjacency list to automatically deduplicate edges — the same pair of words may appear multiple times, and duplicate edges would inflate in-degree counts incorrectly. Initialize in-degree to zero for every character, then increment the neighbor's in-degree each time a new edge is added (after confirming it is not a duplicate).

The total number of unique characters across all words is at most 26 (lowercase English letters), so the graph is always small. Still, the construction logic matters for correctness: missing a character from the in-degree map would cause Kahn's algorithm to skip it, and missing it from the adjacency list would prevent its neighbors from having their in-degrees decremented during BFS.

Kahn's algorithm starts by enqueuing all characters with in-degree zero — these have no prerequisites and can appear first in the ordering. Process the queue: dequeue a character, append it to the result string, then decrement the in-degree of each of its neighbors. When a neighbor's in-degree reaches zero, enqueue it. Repeat until the queue is empty.

The result string builds up the topological order character by character. When the BFS completes, check whether the result string's length equals the total number of unique characters. If they match, you found a valid ordering. If the result is shorter, some characters were never dequeued — meaning they are part of a cycle where every node in the cycle has at least one incoming edge that never gets decremented to zero.

The order in which zero-in-degree nodes are added to the initial queue determines which valid topological ordering you produce when multiple orderings exist. Since the problem accepts any valid ordering, you can use any queue ordering — a simple FIFO queue or even a sorted queue if a specific valid ordering is desired.

The DFS approach to topological sort uses three states per node: unvisited (0), in-progress (1), and done (2). For each unvisited node, run DFS: mark it in-progress, recurse into all neighbors, then mark it done and append it to a result list. If during DFS you encounter an in-progress node, a cycle exists — return invalid immediately.

After DFS completes for all nodes, the result list contains nodes in reverse topological order (last completed is first in topological order). Reverse the list to get the correct ordering. This post-order reversal is the defining characteristic of DFS-based topological sort compared to the direct construction in Kahn's BFS.

For interviews, Kahn's BFS is generally preferred for this problem because it constructs the result directly without reversal, and the cycle detection is an obvious length check rather than the subtler in-progress state check. Both approaches have the same O(V + E) time complexity where V is the number of unique characters and E is the number of ordering edges extracted.

Python BFS solution: from collections import deque, defaultdict. def alienOrder(words): adj={c:set() for w in words for c in w}; indegree={c:0 for c in adj}. For i in range(len(words)-1): w1,w2=words[i],words[i+1]; if len(w1)>len(w2) and w1[:len(w2)]==w2: return "". For c1,c2 in zip(w1,w2): if c1!=c2: if c2 not in adj[c1]: adj[c1].add(c2); indegree[c2]+=1; break. q=deque([c for c in indegree if indegree[c]==0]); res=[]. While q: c=q.popleft(); res.append(c). For nb in adj[c]: indegree[nb]-=1; if indegree[nb]==0: q.append(nb). Return "" if len(res)!=len(indegree) else "".join(res).

Java BFS solution: public String alienOrder(String[] words) { Map<Character,Set<Character>> adj=new HashMap<>(); Map<Character,Integer> indegree=new HashMap<>(); for(String w:words) for(char c:w.toCharArray()){adj.putIfAbsent(c,new HashSet<>());indegree.putIfAbsent(c,0);} for(int i=0;i<words.length-1;i++){String w1=words[i],w2=words[i+1]; if(w1.length()>w2.length()&&w1.startsWith(w2)) return ""; for(int j=0;j<Math.min(w1.length(),w2.length());j++){char c1=w1.charAt(j),c2=w2.charAt(j); if(c1!=c2){if(!adj.get(c1).contains(c2)){adj.get(c1).add(c2);indegree.merge(c2,1,Integer::sum);} break;}}} Queue<Character> q=new LinkedList<>(); for(char c:indegree.keySet()) if(indegree.get(c)==0) q.add(c); StringBuilder sb=new StringBuilder(); while(!q.isEmpty()){char c=q.poll();sb.append(c); for(char nb:adj.get(c)){indegree.merge(nb,-1,Integer::sum); if(indegree.get(nb)==0) q.add(nb);}} return sb.length()==indegree.size()?sb.toString():""; }

Handle edge cases carefully: a single word in the input has no adjacent pairs, so no edges are extracted and all characters are returned in any order. All-same-character words (like ["abc", "abc"]) produce no edges and are valid. The prefix invalidity check — comparing lengths after the zip loop — is the most commonly missed edge case and will cost you in an interview if skipped.

Course Schedule (LeetCode 207) and Course Schedule II (LeetCode 210) are the canonical topological sort problems. LeetCode 207 asks whether a valid course ordering exists (cycle detection only), and LeetCode 210 asks for the actual order (full topological sort). Both use the same Kahn's BFS or DFS 3-state coloring approach. Alien Dictionary applies the same logic but adds the extra step of building the graph from indirect clues in the input data.

Number of Provinces (LeetCode 547) and Accounts Merge (LeetCode 721) are graph connectivity problems using union-find or BFS/DFS. While they do not use topological sort, they share the same graph-building intuition: extract relationships from the input, represent them as edges, then traverse the graph to answer structural questions. Building the character graph for Alien Dictionary uses exactly this pattern.

The topological sort family — Alien Dictionary, Course Schedule I/II, Parallel Courses (LeetCode 1136), and Sequence Reconstruction (LeetCode 444) — all follow the same template: model the problem as a DAG, extract dependency edges, apply Kahn's or DFS topo sort, check for cycles. Mastering one problem in this family makes the others straightforward pattern applications.