Alien Dictionary

You are given a list of words sorted according to the rules of an unknown alien alphabet that uses lowercase English letters. Recover one valid character order that is consistent with the sorted list.

For this question, make the output deterministic: if multiple valid orders exist, return the lexicographically smallest valid order among them. Return an empty string if the word list is invalid or the implied precedence rules contain a cycle. Every distinct letter that appears in words must appear exactly once in the answer.

Input / output

• Input: words: string[]
• Output: string containing each distinct character once, or "" if invalid

Examples

1. words = ["wrt","wrf","er","ett","rftt"] returns "wertf".
2. words = ["z","x"] returns "zx".
3. words = ["abc","ab"] returns "" because a longer word cannot appear before its own prefix.

Constraints

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] contains only lowercase English letters

Target complexity

• Aim for O(total characters + unique letters log unique letters) time.

Hints

1. Compare only adjacent words; the first differing character creates the only ordering edge you can infer from that pair.
2. Once the graph is built, use a topological sort. The lexicographically smallest valid order means you should always take the smallest currently available character first.

Follow-up How would the solution change if the interviewer only needed any valid order instead of the lexicographically smallest one?