Alien Dictionary (Order Derivation)

Alien Dictionary (Derive Character Order) Given a list of words words sorted according to an unknown alien alphabet, derive one possible order of all characters that appear. Rules: For each adjacent pair w1, w2, find the first position where they differ: c1 != c2 implies c1 comes before c2. If w1 is a prefix of w2 but len(w1) > len(w2), the input is invalid: return an empty string. If there is a cycle (no valid topological ordering), also return an empty string. Input Line 1: integer m, number of words. Next m lines: one word per line. Output A string representing any valid character order; print an empty line if impossible. Constraints 1 <= m <= 10^5 Total length of all words <= 2 * 10^5 Provide an exact time and space complexity in terms of V (#unique chars), E (#edges), L (total chars). Example Input: 3 wrt wrf er One valid output: wertf Example Input 3 wrt wrf er Output wertf