Infer an Alien Alphabet from Sorted Words
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given a list of words sorted according to an unknown alphabet.
Return one valid ordering of every distinct character that appears in the
words. If the ordering is invalid or impossible, return an empty string.
When more than one ordering is valid, return the lexicographically smallest
valid ordering under ordinary character order so the output is deterministic.
### Constraints & Assumptions
- The list contains between 1 and 1,000 lowercase words.
- The total number of characters across all words is at most 100,000.
- Every distinct character must appear exactly once in a non-empty result.
- A longer word appearing before its exact prefix makes the input invalid.
### Clarifications
- Only the first differing character in each adjacent word pair creates an ordering constraint.
- Duplicate constraints must not increase a character's in-degree more than once.
- A cycle means no alphabet can satisfy the supplied ordering.
### Examples
```text
words = ["wrt", "wrf", "er", "ett", "rftt"]
output = "wertf"
words = ["abc", "ab"]
output = ""
```
### Hints
```hint Compare neighboring words
Find the first position where each adjacent pair differs; later positions do not add constraints.
```
```hint Make ties deterministic
Consider which topological-sort frontier structure always selects the smallest available character.
```
Quick Answer: Infer a valid alien alphabet from words already sorted in that language. Build precedence constraints from adjacent words, reject invalid prefix orderings and cycles, and produce the lexicographically smallest topological order when several answers are possible.
Given lowercase words claimed to be sorted under an unknown alphabet, return one ordering containing every distinct character exactly once. Compare each adjacent word pair: only its first differing characters create an ordering edge. A longer word before its exact prefix is invalid, and a directed cycle is impossible. Return an empty string for either condition. When several valid orders exist, return the lexicographically smallest one under ordinary character order.
Constraints
- 1 <= len(words) <= 1000.
- All words contain only lowercase English letters.
- The total number of characters is at most 100000.
- Every distinct character appears exactly once in a nonempty result.
- A longer word before its exact prefix is invalid.
- Topological ties use ordinary lexicographic character order.
Examples
Input: (['wrt', 'wrf', 'er', 'ett', 'rftt'],)
Expected Output: 'wertf'
Explanation: The adjacent pairs imply w before e, e before r, r before t, and t before f.
Input: (['abc', 'ab'],)
Expected Output: ''
Explanation: A longer word cannot precede its exact prefix.
Hints
- Only the first differing characters in each adjacent word pair create a constraint.
- Use a min-priority queue for zero-indegree characters to make the result deterministic.