A dictionary of words is sorted by the rules of an alien language that uses lowercase English letters. Derive a letter ordering consistent with it. Return the ordering as a string containing every letter that appears in the words exactly once. When several orderings are consistent, return the lexicographically smallest one (by ordinary a-z). If no ordering is consistent — the words imply a cycle, or a word is followed by its own proper prefix — return the empty string.
Examples
Example 1:
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Example 2:
Input: words = ["z","x"]
Output: "zx"
Example 3:
Input: words = ["z","x","z"]
Output: ""
Explanation: z before x and x before z cannot both hold.
Example 4:
Input: words = ["abc","ab"]
Output: ""
Explanation: a word may not be followed by its own proper prefix.
Example 5:
Input: words = ["ca","cb"]
Output: "abc"
Explanation: only a-before-b is forced; the smallest consistent order places c last... which "abc" does while honouring a < b.
Constraints
1 <= words.length <= 100
1 <= words[i].length <= 20
Words consist of lowercase English letters.
Prerequisites
Graph traversal — DFS and BFS, and a visited set as the thing that makes both terminate. Union-find for connectivity questions; topological order for dependency ones.
How to think about it
1. Adjacent Words Give the Edges Optimal
Intuition
Sorted words say almost nothing individually; the information lives BETWEEN neighbours. The first position where two adjacent words differ gives exactly one ordering fact, and nothing after it is implied. The one illegal case is a word followed by its own prefix, which no ordering can justify. Then it is a topological sort — and because this problem wants the smallest valid order, the queue becomes a min-heap, taking the alphabetically first available letter each round.
Algorithm
1. Seed every letter that appears, so isolated letters are not lost. 2. For each adjacent pair, find the first differing position and add that edge; equal prefixes with the longer word first are impossible. 3. Topologically sort with a min-heap over zero-in-degree letters. 4. Fewer letters emitted than exist means a cycle: return the empty string.
Time & Space
Time O(total letters + alphabet log alphabet). Space O(alphabet).