Determine order of alien alphabet

Q: Determine order of alien alphabet

This question evaluates the ability to infer ordering constraints among characters, model dependencies from ordered examples, and reason about edge cases in lexicographic sequences. Commonly asked in Coding & Algorithms interviews, it assesses both practical algorithmic implementation and conceptual understanding within the domains of string processing and graph-based ordering problems.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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"