Alien Dictionary / Recover Character Order from Sorted Words

Problem: Alien Dictionary Character Order You are given an array of strings words. The words are sorted lexicographically according to an unknown alien alphabet order. Infer the relative order of all characters that appear in words, and output one valid character ordering. If no valid ordering exists, output an empty string. To make the output deterministic, if multiple valid answers exist, output the lexicographically smallest valid ordering. Input Format The first line contains an integer n, the number of words. The next n lines each contain one string word. Output Format Output a string representing the inferred character order. If no valid ordering exists, output an empty string, i.e. an empty line. Constraints 1 <= n <= 1000 1 <= len(words[i]) <= 100 words[i] contains only lowercase English letters 'a' to 'z'. Example 1 Input: 5 wrt wrf er ett rftt Output: wertf Example 2 Input: 3 z x z Output: Explanation: We get both z < x and x < z, so there is a cycle. Example Input 5 wrt wrf er ett rftt Output wertf