An alien language uses lowercase English letters, but in an unknown order. You get words, a list of words from its dictionary that is claimed to be sorted by the alien order (ordinary lexicographic rules: compare at the first differing letter; if one word is a prefix of the other, the shorter one comes first).
Write alien_order(words) -> str that returns a string containing every distinct letter that appears in words, exactly once, in an order under which words really is sorted. If several orders work, return any. If none does, return "".
alien_order(["bca", "bd", "cd", "da"]) # e.g. "bcad", "abcd" or "bacd"
# the words need b before c and c before d; a can go anywhere
alien_order(["zx", "zy"]) # any order with x before y, e.g. "zxy", "xzy", "xyz"
alien_order(["ab", "a"]) # "" (a longer word can't precede its own prefix)
alien_order(["p", "q", "p"]) # "" (p before q and q before p)
Letters that never get constrained still have to appear in the output.
Constraints: up to 100 words of length up to 100.
Show hint
Each pair of neighbouring words tells you at most one fact, at their first differing letter (or that the list can't be sorted, if a longer word comes before its own prefix). Then you need an order of the letters that respects all those facts.