Alien Dictionary (LeetCode 269)
Imagine a freshly invented language built on the same 26 letters we use, except nobody has told you what order those letters actually rank in.
You're handed words, a dictionary-style list of strings from that language, already arranged in the sequence the language's real (but hidden) letter order would produce.
Work out that hidden order: return one string containing every distinct letter that appears across words, arranged from earliest to latest in the language's own ordering. If the list can't have come from any consistent ordering, return "" instead. If more than one ordering fits the evidence, returning any one of them is accepted.
Worked Examples
words = ["wrt","wrf","er","ett","rftt"]"wertf"wrt/wrf puts t before f, wrf/er puts w before e, er/ett puts r before t, and ett/rftt puts e before r. Together: w, e, r, t, f.words = ["z","x"]"zx"z comes before x in the list, so z ranks first.words = ["z","x","z"]""⚖️Formal Constraints & Bounds
1 <= words.length <= 1001 <= words[i].length <= 100words[i]consists of only lowercase English letters.
Core Insight
First differing character between adjacent sorted words uniquely defines order constraints.
Real-World Scenario & Production Applications
Deciphering unknown sequential ordering from comparative data, sorting key inference.
Step-by-Step Execution Trace Table
| Word Pair | Differing Chars | Extracted Directed Edge |
|---|---|---|
| 'wrt' vs 'wrf' | 't' != 'f' | t -> f |
| 'wrf' vs 'er' | 'w' != 'e' | w -> e |
| 'er' vs 'ett' | 'r' != 't' | r -> t |
| 'ett' vs 'rftt' | 'e' != 'r' | e -> r |
| Topological Order | 'w' -> 'e' -> 'r' -> 't' -> 'f' | 'wertf' |
words = ["wrt","wrf","er","ett","rftt"]"wertf"| Word Pair | Differing Chars | Extracted Directed Edge |
|---|---|---|
| 'wrt' vs 'wrf' | 't' != 'f' | t -> f |
| 'wrf' vs 'er' | 'w' != 'e' | w -> e |
| 'er' vs 'ett' | 'r' != 't' | r -> t |
| 'ett' vs 'rftt' | 'e' != 'r' | e -> r |
| Topological Order | 'w' -> 'e' -> 'r' -> 't' -> 'f' | 'wertf' |
| 1 | adj = {c: set() for c in all_chars} |
| 2 | in_degree = {c: 0 for c in all_chars} |
| 3 | compare adjacent words to find first differing char edge w1[j] -> w2[j] |
| 4 | queue = deque(chars with in_degree 0) |
| 5 | order = [] |
| 6 | while queue: |
| 7 | c = queue.popleft() |
| 8 | order.append(c) |
| 9 | for nxt in adj[c]: |
| 10 | in_degree[nxt] -= 1 |
| 11 | if in_degree[nxt] == 0: |
| 12 | queue.append(nxt) |
| 13 | return ''.join(order) if len(order) == len(in_degree) else '' |
Conceptual Narrative
Alien Dictionary reconstructs an unknown alphabet's lexicographical order by extracting pairwise character precedence constraints from a sorted word list.
🧭 Conceptual Foundation & Pattern Intuition
Given lexicographically sorted words in an alien language, deduce the alphabetical order. Comparing adjacent words w1 and w2 identifies the first mismatching character w1[k] != w2[k], proving w1[k] precedes w2[k] (). Topological sorting on the resulting character DAG(Directed Acyclic Graph) yields the alphabet.
🏟️ The Analogy: Stone Tablet Inscriptions
Archaeologists find a stone ledger of sorted words. Comparing 'apple' and 'apply' proves 'e' precedes 'y'. Comparing 'zebra' and 'zoo' proves 'e' precedes 'o'. Stitching these pairwise clues together reconstructs the complete alphabet.
🔑 Why It Works
Prefix Invalidity Trap: If word 2 is a strict prefix of word 1 (e.g. ['abc', 'ab']), the dictionary is fundamentally invalid (like 'apple' appearing before 'app' in English). Return '' immediately.
Prefix truncation invalidity: Failing to detect
['abc', 'ab']where a longer word precedes its own prefix; this is an invalid lexicographical order and must return''.Comparing non-adjacent word pairs: Comparing all word pairs generates redundant edges and false transitive cycles; comparing adjacent words is necessary and sufficient.
Missing isolated characters: Dropping characters that appear in words but have zero incoming or outgoing edges from the final result string.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Inferring total ordering from lexicographically sorted sequences.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: character adjacency graph is a DAG(Directed Acyclic Graph) if and only if alphabet order is valid.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Cycles in character ordering: e.g. ['z', 'x', 'z'] creates z -> x and x -> z cycle.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I create adjacency and in-degree maps for all unique characters. I compare adjacent words to find the first differing character, creating a directed edge
w1[j] -> w2[j]. If word 1 has word 2 as prefix, I return ''. I run Kahn's algorithm to produce the order string. Runs in O(C) total characters time and O(U) unique characters space."
Complexity & Mathematical Proof
O(C)
Look at the execution steps: Let C be total length of all words in word list, V be number of unique characters (<= 26), and E be derived precedence edges. Deriving edges takes O(C); Kahn's topological sort takes O(V + E). Total O(C).
O(V + E) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Adjacency list and in-degree map for at most 26 lowercase English letters, taking O(1) bounded auxiliary space (or O(V + E)).
T(C) = O(C) + O(V + E) = O(C)
Derivation Progression
for (w1, w2) in pairs: find first differing char
Extracts directed dependency u -> v in O(C) total string comparisons.
if w1 starts with w2 and |w1| > |w2|: return ""
Catches prefix violations in O(min(|w1|, |w2|)).
O(V + E) ≤ O(26 + 262) = O(1)
Kahn's BFS emits unique alien character order.
Variable Definitions
Total combined character length across all dictionary words
Number of unique alien alphabet letters (at most 26)
Derived character precedence ordering edges (at most 26^2)
Memory Architecture & Bounds
O(1) Iterative
O(1) Graph bounded by 26 lowercase English letters
O(V) Character order string (<= 26 chars)
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "alien language sorted lexicographically", "reconstruct alphabet order". Order reconstruction from adjacent sorted pairs: for words and , the first differing character w_{2} establishes a directed edge $$w_{1}w_{2}. A Senior SWE constructs the letter DAG(Directed Acyclic Graph) and runs Kahn's Algorithm.
Words , length . Alphabet size . Time budget where is total characters across all words.
Prefix Invalidation Trap: If starts with but (e.g. "apple" before "app"), the dictionary is invalid: return "" immediately!
Alien Dictionary (LeetCode 269)
Imagine a freshly invented language built on the same 26 letters we use, except nobody has told you what order those letters actually rank in.
You're handed words, a dictionary-style list of strings from that language, already arranged in the sequence the language's real (but hidden) letter order would produce.
Work out that hidden order: return one string containing every distinct letter that appears across words, arranged from earliest to latest in the language's own ordering. If the list can't have come from any consistent ordering, return "" instead. If more than one ordering fits the evidence, returning any one of them is accepted.
Worked Examples
words = ["wrt","wrf","er","ett","rftt"]"wertf"wrt/wrf puts t before f, wrf/er puts w before e, er/ett puts r before t, and ett/rftt puts e before r. Together: w, e, r, t, f.words = ["z","x"]"zx"z comes before x in the list, so z ranks first.words = ["z","x","z"]""⚖️Formal Constraints & Bounds
1 <= words.length <= 1001 <= words[i].length <= 100words[i]consists of only lowercase English letters.
Core Insight
First differing character between adjacent sorted words uniquely defines order constraints.
Real-World Scenario & Production Applications
Deciphering unknown sequential ordering from comparative data, sorting key inference.
Step-by-Step Execution Trace Table
| Word Pair | Differing Chars | Extracted Directed Edge |
|---|---|---|
| 'wrt' vs 'wrf' | 't' != 'f' | t -> f |
| 'wrf' vs 'er' | 'w' != 'e' | w -> e |
| 'er' vs 'ett' | 'r' != 't' | r -> t |
| 'ett' vs 'rftt' | 'e' != 'r' | e -> r |
| Topological Order | 'w' -> 'e' -> 'r' -> 't' -> 'f' | 'wertf' |
words = ["wrt","wrf","er","ett","rftt"]"wertf"| Word Pair | Differing Chars | Extracted Directed Edge |
|---|---|---|
| 'wrt' vs 'wrf' | 't' != 'f' | t -> f |
| 'wrf' vs 'er' | 'w' != 'e' | w -> e |
| 'er' vs 'ett' | 'r' != 't' | r -> t |
| 'ett' vs 'rftt' | 'e' != 'r' | e -> r |
| Topological Order | 'w' -> 'e' -> 'r' -> 't' -> 'f' | 'wertf' |
| 1 | adj = {c: set() for c in all_chars} |
| 2 | in_degree = {c: 0 for c in all_chars} |
| 3 | compare adjacent words to find first differing char edge w1[j] -> w2[j] |
| 4 | queue = deque(chars with in_degree 0) |
| 5 | order = [] |
| 6 | while queue: |
| 7 | c = queue.popleft() |
| 8 | order.append(c) |
| 9 | for nxt in adj[c]: |
| 10 | in_degree[nxt] -= 1 |
| 11 | if in_degree[nxt] == 0: |
| 12 | queue.append(nxt) |
| 13 | return ''.join(order) if len(order) == len(in_degree) else '' |
Conceptual Narrative
Alien Dictionary reconstructs an unknown alphabet's lexicographical order by extracting pairwise character precedence constraints from a sorted word list.
🧭 Conceptual Foundation & Pattern Intuition
Given lexicographically sorted words in an alien language, deduce the alphabetical order. Comparing adjacent words w1 and w2 identifies the first mismatching character w1[k] != w2[k], proving w1[k] precedes w2[k] (). Topological sorting on the resulting character DAG(Directed Acyclic Graph) yields the alphabet.
🏟️ The Analogy: Stone Tablet Inscriptions
Archaeologists find a stone ledger of sorted words. Comparing 'apple' and 'apply' proves 'e' precedes 'y'. Comparing 'zebra' and 'zoo' proves 'e' precedes 'o'. Stitching these pairwise clues together reconstructs the complete alphabet.
🔑 Why It Works
Prefix Invalidity Trap: If word 2 is a strict prefix of word 1 (e.g. ['abc', 'ab']), the dictionary is fundamentally invalid (like 'apple' appearing before 'app' in English). Return '' immediately.
Prefix truncation invalidity: Failing to detect
['abc', 'ab']where a longer word precedes its own prefix; this is an invalid lexicographical order and must return''.Comparing non-adjacent word pairs: Comparing all word pairs generates redundant edges and false transitive cycles; comparing adjacent words is necessary and sufficient.
Missing isolated characters: Dropping characters that appear in words but have zero incoming or outgoing edges from the final result string.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Inferring total ordering from lexicographically sorted sequences.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: character adjacency graph is a DAG(Directed Acyclic Graph) if and only if alphabet order is valid.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Cycles in character ordering: e.g. ['z', 'x', 'z'] creates z -> x and x -> z cycle.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I create adjacency and in-degree maps for all unique characters. I compare adjacent words to find the first differing character, creating a directed edge
w1[j] -> w2[j]. If word 1 has word 2 as prefix, I return ''. I run Kahn's algorithm to produce the order string. Runs in O(C) total characters time and O(U) unique characters space."
Complexity & Mathematical Proof
O(C)
Look at the execution steps: Let C be total length of all words in word list, V be number of unique characters (<= 26), and E be derived precedence edges. Deriving edges takes O(C); Kahn's topological sort takes O(V + E). Total O(C).
O(V + E) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Adjacency list and in-degree map for at most 26 lowercase English letters, taking O(1) bounded auxiliary space (or O(V + E)).
T(C) = O(C) + O(V + E) = O(C)
Derivation Progression
for (w1, w2) in pairs: find first differing char
Extracts directed dependency u -> v in O(C) total string comparisons.
if w1 starts with w2 and |w1| > |w2|: return ""
Catches prefix violations in O(min(|w1|, |w2|)).
O(V + E) ≤ O(26 + 262) = O(1)
Kahn's BFS emits unique alien character order.
Variable Definitions
Total combined character length across all dictionary words
Number of unique alien alphabet letters (at most 26)
Derived character precedence ordering edges (at most 26^2)
Memory Architecture & Bounds
O(1) Iterative
O(1) Graph bounded by 26 lowercase English letters
O(V) Character order string (<= 26 chars)
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "alien language sorted lexicographically", "reconstruct alphabet order". Order reconstruction from adjacent sorted pairs: for words and , the first differing character w_{2} establishes a directed edge $$w_{1}w_{2}. A Senior SWE constructs the letter DAG(Directed Acyclic Graph) and runs Kahn's Algorithm.
Words , length . Alphabet size . Time budget where is total characters across all words.
Prefix Invalidation Trap: If starts with but (e.g. "apple" before "app"), the dictionary is invalid: return "" immediately!