269. Alien Dictionary
Asked at Google, Meta, Amazon, Microsoft and 2 more
Difficulty
Hard
Time
O(C)
Space
O(1)
Pattern
Graph
Companies
6
Problem
You are given a list of words from an alien language. This language uses the same 26 letters as English, but the alphabet order is different and unknown to you.
The words are claimed to be sorted in lexicographic order using that unknown alphabet. Your job is to figure out one valid letter order. Return any string of the distinct letters that is consistent with the sorted list.
If no letter order can make the list sorted, return an empty string "". One special case makes the list invalid: if a word is a prefix of the word right after it but is longer (for example "abc" before "ab"), no alphabet can explain that, so the answer is "".
Turn word pairs into letter rules
Constraints
- ●
1 <= words.length <= 100 - ●
1 <= words[i].length <= 100 - ●
words[i] consists of only lowercase English letters
Examples
words = ["wrt","wrf","er","ett","rftt"]wertfwords = ["z","x"]"zx"words = ["z","x","z"]""Asked At
6 companies| Company | Difficulty | |
|---|---|---|
| Hard | View all Google questions → | |
| Meta | Hard | View all Meta questions → |
| Amazon | Hard | View all Amazon questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Apple | Hard | View all Apple questions → |
| Uber | Hard | View all Uber questions → |
How to Think About It
Compare adjacent words to find the first differing character. That gives an ordering constraint: char A comes before char B (edge from A to B in the graph).
Build a graph of character ordering. Each edge A→B means A must come before B in the alien alphabet.
Topological sort the graph to get the character order. Use Kahn's algorithm (BFS) with in-degree tracking.
Cycle detection: if the topological sort result has fewer characters than the total unique chars, a cycle exists (invalid input).
Edge cases: single word (any order of its chars), invalid input where a longer word comes before its prefix.
Optimal Approach
Step 1: Build adjacency list from adjacent word comparisons. Find first differing char between each pair.
Step 2: Compute in-degrees for all characters.
Step 3: Kahn's algorithm — start with chars that have in-degree 0. For each, add to result, decrement in-degrees of neighbors.
Step 4: If result length < total unique chars, a cycle exists — return "".
Time: O(C) where C is total characters across all words. Space: O(1) — at most 26 nodes.
Topological sort of the letter graph
What Trips People Up in Real Interviews
Getting the edge direction wrong. If word1 comes before word2 and they differ at position i, the edge is word1[i] → word2[i] (word1[i] comes first in the alphabet).
Not detecting cycles. If the topological sort result is shorter than the number of unique characters, a cycle exists — return empty string.
Forgetting that a longer word coming before its prefix is invalid. If "abc" comes before "ab", that's impossible — return empty.
Not handling single-word input. With one word, any ordering of its characters is valid.
Adding edges for every differing character instead of just the first one. Only the FIRST differing character between adjacent words gives a reliable ordering constraint. Subsequent differences don't.
Solution Code
O(C) timefrom collections import deque
def alienOrder(words):
adj = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
return ""
for j in range(min_len):
if w1[j] != w2[j]:
adj[w1[j]].add(w2[j])
break
in_degree = {c: 0 for c in adj}
for c in adj:
for neighbor in adj[c]:
in_degree[neighbor] += 1
q = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while q:
c = q.popleft()
result.append(c)
for neighbor in adj[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
q.append(neighbor)
return "".join(result) if len(result) == len(adj) else ""Frequently Asked Questions
What is the Alien Dictionary problem?
Given a sorted list of words in an alien language, find the order of characters in that language. This is a topological sort problem disguised as a string problem.
How do you solve Alien Dictionary?
The optimal approach runs in O(C) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Alien Dictionary?
Alien Dictionary is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a hard difficulty problem.
What are common mistakes on Alien Dictionary?
- Getting the edge direction wrong. If word1 comes before word2 and they differ at position i, the edge is `word1[i]` → `word2[i]` (`word1[i]` comes first in the alphabet).
- Not detecting cycles. If the topological sort result is shorter than the number of unique characters, a cycle exists — return empty string.
- Forgetting that a longer word coming before its prefix is invalid. If "abc" comes before "ab", that's impossible — return empty.
- Not handling single-word input. With one word, any ordering of its characters is valid.
- Adding edges for every differing character instead of just the first one. Only the FIRST differing character between adjacent words gives a reliable ordering constraint. Subsequent differences don't.