Alien Dictionary

Problem

A deep-space probe returns a list of words from an alien language, sorted lexicographically by that language's rules. The alphabet is the same 26 lowercase letters with an unknown order. Reconstruct any valid alphabet order consistent with the sorted word list, or report impossibility when no order can explain the input.

Example 1:

Input: words = ["ba", "ca", "cb", "db"]
Output: "abcd"
Explanation: ba < ca forces b before c; ca < cb forces a before b; cb < db forces c before d. The chain a -> b -> c -> d is fully forced.

Example 2:

Input: words = ["abc", "ab"]
Output: ""
Explanation: "abc" cannot precede its own prefix "ab" in any alphabet - no valid order exists.

Example 3:

Input: words = ["abc", "acd", "abd"]
Output: ""
Explanation: abc < acd forces b < c, but acd < abd forces c < b - the rules form a cycle.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of lowercase English letters.
• All the strings in words are unique.

Solution Breakdown

Approach - extract precedence edges from adjacent word pairs, then Kahn's topological sort with impossibility detection.

The sorted word list speaks only through adjacent pairs, and each pair speaks only at its first differing character: everything before that position is shared context, and comparing characters after a resolved difference would invent rules the input never implied. So for each adjacent pair, scan to the first difference and record one edge - left word's character must precede right word's character. Two special cases end the analysis early. If the scan exhausts the second word while the first still has characters, a longer word is asked to precede its own prefix - impossible in any alphabet, return "". And if the collected edges contain a cycle, no linear order satisfies them all. Every character appearing anywhere in the list joins the graph as a node even when no rule constrains it - the answer must be the full alien alphabet seen in the input, and unconstrained letters simply enter the output whenever their indegree (zero forever) lets them.

Kahn's algorithm surfaces both the order and the cycle verdict: seed a queue with every indegree-zero character (sorted, so ties among unconstrained letters break deterministically), repeatedly pop a character to the output and decrement the indegrees of everything it precededes, and finish. If the output is shorter than the node count, the stranded nodes sit on a cycle - return "". Trace ["ba", "ca", "cb", "db"]: pairs give b < c (ba vs ca at index 0), a < b (ca vs cb at index 1), c < d (cb vs db at index 0) - a single forced chain whose unique topological order is abcd. The cycle case ["abc", "acd", "abd"] yields b < c and c < b; neither node ever reaches indegree zero, the queue drains early, and the length check fails.

Edge cases - single-word or all-same-letter inputs leave every character unconstrained, so the sorted ready-set order is returned (any permutation would be valid on the real problem, the sort is just the determinism convention); duplicate rules across pairs are deduplicated by the seen-set so indegrees never double-count; the prefix violation check must fire before any edge work, since no graph can represent an unsatisfiable input.

Complexity - O(C) to collect characters plus O(total letters scanned) for pair comparisons plus O(V + E) for Kahn's - with V at most 26 letters and E at most 26 * 25, effectively linear in the input size; O(V + E) space for adjacency, indegrees, and the seen-set, all bounded by the 26-letter alphabet.