76. Alien Dictionary

Hard · Graph

You are given a list of words from an alien dictionary in lexicographic order. Your task is to derive the alphabet order of that alien language and return all letters that appear, sorted in the correct order.

The input is an array of words (strings) already sorted according to the alien alphabet. By comparing adjacent words, you can deduce which letters come before others. When multiple valid orderings exist, return the lexicographically smallest one (use a min-heap or sorted approach when selecting which letter to process next).

If the input is inconsistent (for example, a longer word comes before its prefix, which would violate any valid ordering), return an empty string ''.

Return a string containing all unique letters from the input, arranged in the derived alien alphabet order.

Examples

Example 1
Input: ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Explanation: Lex-smallest valid order
Example 2
Input: ["abc","ab"]
Output: ""
Explanation: Inconsistent (a longer word that is a prefix of another)

Constraints