Compile Ready
Module 4 · Topological Sort

Alien Dictionary

HardProblem 13 of 25 11 min read ~30 min to solve LeetCode
GraphTopological SortBFSString
Asked atGoogleAmazonMicrosoftMetaAirbnb

Problem Statement

You are given a list of words sorted lexicographically according to an unknown alien alphabet. Return any valid ordering of the distinct letters that appear in the words. If the sorted list is inconsistent and no valid alphabet exists, return the empty string.

The only ordering evidence comes from adjacent words: at the first position where two neighbouring words differ, the letter from the first word must come before the letter from the second word. If the earlier word is longer and the later word is its prefix, such as abc before ab, the input is invalid immediately.

Input

An array words that is claimed to be sorted by an unknown alphabet. Only letters that appear in the words should appear in the output.

Output

A string containing one valid ordering of the seen letters, or the empty string if the constraints are contradictory.

Constraints

  • •1 <= words.length <= 100
  • •1 <= words[i].length <= 100
  • •words[i] consists of lowercase English letters
  • •All words are sorted according to the alien language if a valid order exists

Examples

Example 1

Input: 
words = ['wrt','wrf','er','ett','rftt']
Output: wertf
Explanation: Comparisons imply w → e, r → t, t → f, and e → r. One valid order satisfying all edges is wertf.

Example 2

Input: 
words = ['z','x']
Output: zx
Explanation: The first differing characters give z → x, so z must come before x.

Example 3

Input: 
words = ['z','x','z']
Output: empty string
Explanation: The first pair implies z → x, while the second pair implies x → z. That cycle makes every alphabet invalid.

Example 4

Input: 
words = ['abc','ab']
Output: empty string
Explanation: The later word is a prefix of the earlier longer word, which can never happen in a valid lexicographic ordering.

Learning Objectives

  • Derive graph edges from the first differing character in each adjacent word pair.
  • Handle the invalid prefix case before topological sorting.
  • Topologically sort only the letters that actually appear in the input.
  • Avoid duplicate edges so indegrees remain accurate.

Intuition

The words are already sorted, so every adjacent pair is a clue about the alien alphabet. Compare two neighbouring words from left to right. As soon as their characters differ, lexicographic order says the first word's character must be smaller than the second word's character. That single comparison creates one directed edge. Characters after the first difference tell you nothing, because lexicographic order was decided earlier.

The prefix case is the trap. In any lexicographic system, a shorter word must come before its longer extension. Therefore ab can appear before abc, but abc before ab is impossible no matter how letters are ordered. You must reject that before building a misleading graph.

After all edges are collected, the problem becomes Course Schedule II over letters instead of courses. Kahn's algorithm emits letters with no remaining prerequisites. If a cycle remains, the queue dries up too early and the output length is smaller than the number of distinct seen letters.

Common mistakes

  • ×Adding edges from every differing character position. Only the first difference matters.
  • ×Missing the invalid prefix case where the first word is longer and the second word is its exact prefix.
  • ×Including all 26 letters in the result instead of only letters that appear in the input.
  • ×Counting duplicate edges multiple times, which inflates indegree and falsely creates a cycle.
  • ×Assuming there is a unique answer. Many valid alphabets can satisfy the same constraints.

Algorithm Explanation

  1. Create graph storage for 26 lowercase letters, plus a seen array. Mark every character that appears and count distinct seen letters.
  2. For each adjacent pair of words, scan until the first differing index or until one word ends.
  3. If no difference exists and the first word is longer, return the empty string because the prefix order is invalid.
  4. If a first difference exists, add an edge firstChar → secondChar. Only increment indegree the first time that edge is added.
  5. Enqueue every seen letter with indegree 0.
  6. Run Kahn's algorithm, appending each popped letter to the answer and decrementing its outgoing neighbours.
  7. Return the answer only if its length equals the number of seen letters; otherwise a cycle made the dictionary invalid.

Solutions

Solution: Kahn's topological sort over seen letters

Extract precedence edges from adjacent word pairs, reject invalid prefixes immediately, then run Kahn's algorithm on the distinct letters that actually appear.

Step-by-step

  1. Initialise 26 adjacency sets so duplicate edges are naturally ignored.
  2. Mark all letters seen while scanning all words.
  3. Compare words[i] and words[i + 1]. The first different characters form an edge; if there is no difference and the first word is longer, return empty.
  4. Seed the queue with seen letters whose indegree is 0.
  5. Pop letters into a StringBuilder and relax outgoing edges.
  6. If the StringBuilder length is smaller than the number of seen letters, a cycle exists, so return empty.
Time

O(C + A)

Space

O(A)

C is the total number of characters scanned; A is bounded by 26 letters and their edges.

Java implementation

Loading…

Dry Run

Sample input

words = ['wrt','wrf','er','ett','rftt']. Compare adjacent pairs and then run Kahn's algorithm on the seen letters {w,r,t,f,e}.

StepEvidenceEdge addedZero-indegree queueOrder so far
Compare 1wrt vs wrf first differs at t/ft → f--
Compare 2wrf vs er first differs at w/ew → e--
Compare 3er vs ett first differs at r/tr → t--
Compare 4ett vs rftt first differs at e/re → r[w]
Kahn 1pop wdecrement e[e]w
Kahn 2pop edecrement r[r]we
Kahn 3pop rdecrement t[t]wer
Kahn 4pop tdecrement f[f]wert
Kahn 5pop fnone[]wertf

The output length is 5, which matches the five seen letters, so there is no cycle. The inferred chain w → e → r → t → f yields wertf.

Interview Tips

Lead with the edge-extraction rule, not with topological sort. Interviewers are testing whether you know what evidence a sorted dictionary actually provides. State the prefix invalid case explicitly before coding; it is the most common missed edge case. Use sets for adjacency so duplicate constraints do not corrupt indegrees, and remind the interviewer that any valid character order is acceptable.

Likely follow-ups

  • Return the lexicographically smallest valid alien order by using a min-heap for zero-indegree letters.
  • Detect whether the alien order is unique or whether multiple answers are possible.
  • Support arbitrary Unicode symbols instead of only lowercase English letters.
  • Given a proposed alphabet, verify whether the word list is sorted under it.

Similar Problems

Course Schedule II
MediumSame topological sort once letter constraints are extracted.
Course Schedule
MediumCycle detection in the dependency graph.
Parallel Courses
Medium
Verifying an Alien Dictionary
EasyChecks a known order instead of inferring one.

Key Takeaways

  • Adjacent sorted words reveal one edge from their first differing character only.
  • A longer word before its own prefix is impossible and must return empty immediately.
  • Topologically sort only characters that appear in the input.
  • Duplicate edges must not increment indegree more than once.
  • A shorter-than-seen output means a cycle in the inferred alphabet.
Reusable template: Infer precedence edges from first differences, reject invalid prefixes, then Kahn-sort the seen characters and validate output length.