Reconstruct the Alphabet Order of an Alien Language
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Reconstruct the Alphabet Order of an Alien Language
A research team has intercepted a list of words written in an alien language. The words use lowercase English letters `a`–`z`, but the alphabetical order of those letters in the alien language is **unknown** and may differ from English.
You are given a list of words `words`, and you are told that this list is sorted in **lexicographic (dictionary) order according to the alien language's letter ordering**. Your task is to recover a possible ordering of the letters.
Return a string containing all distinct letters that appear in `words`, arranged so that the string respects the alien lexicographic order. If there are multiple valid orderings, return any one of them. If no valid ordering exists (the input is internally contradictory), return the empty string `""`.
### Lexicographic ordering rules
Lexicographic order between two words is determined the same way as in English, but using the alien letter ranking:
1. Compare the two words character by character from left to right.
2. At the first position where the characters differ, the word whose character ranks earlier in the alien order comes first.
3. If one word is a prefix of the other (all compared characters are equal up to the length of the shorter word), then the **shorter word must come first**. A list in which a longer word appears immediately before one of its own prefixes is invalid.
### Examples
Example 1:
```
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
```
Explanation: From `"wrt"` before `"wrf"` we deduce `t` comes before `f`. From `"wrf"` before `"er"` we deduce `w` comes before `e`. From `"er"` before `"ett"` we deduce `r` comes before `t`. From `"ett"` before `"rftt"` we deduce `e` comes before `r`. One ordering consistent with all of these is `"wertf"`.
Example 2:
```
Input: words = ["z", "x"]
Output: "zx"
```
Example 3 (contradiction):
```
Input: words = ["z", "x", "z"]
Output: ""
```
Explanation: `z` before `x` and `x` before `z` cannot both hold, so no valid ordering exists.
Example 4 (invalid prefix ordering):
```
Input: words = ["abc", "ab"]
Output: ""
```
Explanation: `"abc"` cannot come before its own prefix `"ab"`, so the list is not validly sorted.
### Constraints
- `1 <= words.length <= 100`
- `1 <= words[i].length <= 100`
- All characters in `words[i]` are lowercase English letters.
- The output must contain each distinct letter that appears in `words` exactly once, and no other letters.
### Required function
Implement:
```
def alien_order(words: list[str]) -> str
```
It returns a valid letter ordering as described, or `""` if none exists.
Quick Answer: This question tests graph construction and topological sorting, core algorithmic skills for reasoning about partial orderings derived from constraints. It evaluates practical application of directed acyclic graphs and cycle detection, competencies commonly assessed in software engineering interviews when gauging depth in graph algorithms and edge-case handling.
A research team has intercepted a list of words written in an alien language. The words use lowercase English letters `a`-`z`, but the alphabetical order of those letters in the alien language is **unknown** and may differ from English.
You are given a list of words `words`, sorted in **lexicographic (dictionary) order according to the alien language's letter ordering**. Recover a possible ordering of the letters.
Return a string containing all distinct letters that appear in `words`, arranged so that the string respects the alien lexicographic order. If multiple valid orderings exist, return any one of them (this console's reference solution returns the alphabetically-smallest valid ordering so the answer is deterministic). If no valid ordering exists (the input is internally contradictory), return the empty string `""`.
### Lexicographic ordering rules
1. Compare two adjacent words character by character, left to right.
2. At the first position where they differ, the word whose character ranks earlier in the alien order comes first.
3. If one word is a prefix of the other, the **shorter word must come first**. A list where a longer word appears immediately before one of its own prefixes is invalid.
### Examples
```
Input: ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf"
Input: ["z", "x"] Output: "zx"
Input: ["z", "x", "z"] Output: "" (contradiction)
Input: ["abc", "ab"] Output: "" (invalid prefix order)
```
### Constraints
- `1 <= words.length <= 100`
- `1 <= words[i].length <= 100`
- All characters are lowercase English letters.
- The output must contain each distinct letter appearing in `words` exactly once, and no others.
Constraints
- 1 <= words.length <= 100
- 1 <= words[i].length <= 100
- All characters in words[i] are lowercase English letters a-z.
- The output must contain each distinct letter appearing in words exactly once and no others.
- Return "" when the ordering is contradictory (cycle) or a longer word precedes its own prefix.
Examples
Input: (["wrt", "wrf", "er", "ett", "rftt"],)
Expected Output: "wertf"
Explanation: t<f (wrt vs wrf), w<e (wrf vs er), r<t (er vs ett), e<r (ett vs rftt). The unique alphabetically-smallest topological order consistent with w<e<r<t<f is "wertf".
Input: (["z", "x"],)
Expected Output: "zx"
Explanation: z before x at the first character, so z ranks before x: "zx".
Input: (["z", "x", "z"],)
Expected Output: ""
Explanation: z<x from the first pair and x<z from the second pair form a cycle; no valid ordering exists.
Input: (["abc", "ab"],)
Expected Output: ""
Explanation: "abc" cannot precede its own prefix "ab" (longer word before its prefix is invalid).
Input: (["ba", "bc", "ac", "ad"],)
Expected Output: "bacd"
Explanation: ba<bc gives a<c; bc<ac gives b<a; ac<ad gives c<d. Chain b<a<c<d forces the unique order "bacd".
Input: (["abc"],)
Expected Output: "abc"
Explanation: A single word imposes no ordering constraints, so the three distinct letters come out in alphabetical (deterministic) order: "abc".
Input: (["a"],)
Expected Output: "a"
Explanation: Single letter, single word -> just "a".
Input: (["abc", "abc"],)
Expected Output: "abc"
Explanation: Two identical adjacent words are prefix-equal (valid) and add no edges; letters emerge alphabetically as "abc".
Hints
- Model letters as graph nodes. Each adjacent pair of words gives at most one ordering edge: at the FIRST differing character position, the earlier word's letter ranks before the later word's letter.
- Before building an edge, handle the invalid-prefix case: if word i and word i+1 share a common prefix but word i is longer (no differing character found), the list is unsorted -> return "".
- Run a topological sort (Kahn's algorithm). If you cannot output every distinct letter (a cycle remains), the constraints are contradictory -> return "".
- To make the result deterministic when several orderings are valid, pop the smallest available letter each step using a min-heap / priority queue.