Alien Dictionary
Problem Statement
You get a list of words. The words are in the dictionary order of an alien language. The alien alphabet uses lowercase letters, but their order is unknown.
Find a letter order that makes the list sorted. Return every letter that appears in the words, once each, in that order, as one string.
Any valid order is accepted. If no order can make the list sorted, return an empty string. That happens when two rules clash, or when a longer word comes before its own prefix.
words: a list of strings in the alien dictionary order (the order may be impossible).
One string with each letter that appears in words once, in a valid alien order. Or an empty string if none exists.
wrt vs wrf gives t before f. wrf vs er gives w before e. er vs ett gives r before t. ett vs rftt gives e before r. Those rules form one chain: w, e, r, t, f.
z vs x says z comes before x. That is the only order.
z before x, then x before z. Those two rules form a cycle, so no order works.
- • Every word uses only lowercase letters a to z.
- • Some inputs have no valid order. For those, return an empty string.
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Try each order of the letters; keep the first one that keeps the list sorted
Rule per pair from its first difference; prefix check; Kahn over letters that appear
The answer uses each letter that appears exactly once, so it is one order of those letters. Try every order. For each one, check that every word is at most the word after it, comparing letters by their place in that order. A shorter word that matches the start of a longer one counts as smaller. The first order that passes is the answer.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.