Alien Dictionary
Hard · Graphs · about 35 minutes
Asked at Meta, Google, Amazon, Uber, Airbnb, Bloomberg, Goldman Sachs, JPMorgan Chase, Booking.com, Expedia Group, Zillow, Yelp.
An unknown language writes with lowercase English letters but sorts them in its own order. words is a list already sorted by that order. Work out the alphabet: return the distinct letters appearing in words, arranged in the language's order. If words can't be sorted under any order (the clues contradict each other, or a longer word is listed ahead of its own prefix), return "". In general several alphabets can fit; the tests here have only one.