Determine order of alien alphabet

You are given a list of words sorted in lexicographic order according to an unknown ("alien") alphabet.

Task

Return one valid ordering of the unique characters in this alien alphabet that is consistent with the given sorted word list. If no valid ordering exists, return an empty string.

Details

• The alien alphabet contains exactly the set of distinct characters that appear in the input words.
• The input list words is already sorted according to the alien alphabet.
• If multiple valid character orders exist, you may return any one of them.

Input

• words : an array of strings, length n .

Output

• A string containing all distinct characters exactly once in a valid order, or "" if impossible.

Constraints (typical interview bounds)

• 1 <= n <= 10^4
• 1 <= len(words[i]) <= 100
• Characters are lowercase English letters (you can assume an upper bound of 26 unique characters).

Notes / Edge cases

• If word1 is a strict prefix of word2 , then word1 must appear before word2 in the sorted list (otherwise the ordering is invalid).

Example

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]

Possible output: "wertf"