An alien language writes with lowercase English letters, but it ranks them in an order of its own that you don't know. You are given words, a list taken from that language's dictionary. The list is already sorted by the alien order, using the same rule as an ordinary dictionary:
Find an order of the letters under which words is sorted. Return it as a string that holds every letter appearing in words, each exactly once, from the earliest-ranked to the latest.
""."pz" before "pa" puts z ahead of a. "pa" before "za" puts p ahead of z. Together they fix the order p, z, a.
The words show that b ranks before a and a before d. Nothing pins down c, so "bacd", "bcad", "cbad" and "badc" all fit. "bacd" is the first of them alphabetically.
"mo" is a prefix of "mop", so it must come first in any order. The list has it second, so no order fits.
Constraints
1 <= words.length <= 1001 <= words[i].length <= 100words[i] consists of lowercase English letters."".Only neighbouring words tell you anything, and only at the first position where they differ: that pair of letters says which one ranks earlier. If two neighbours never differ and the first is longer, no order can work.
The sorted list is a set of clues, and each clue sits between two neighbouring words. Line them up and find the first position where they differ: the letter in the earlier word ranks before the letter in the later word. That one position is the whole clue. Everything after it says nothing, because the first difference already decided the order of the two words.
Time O(C + U · 26)Space O(26²)
The full walkthrough and code are part of Premium