Loading problem…
There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language, and return it. If there are multiple valid orderings, return any of them. If the order is invalid, return an empty string.
Example 1
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: wertf
Explanation: Comparing neighbouring words at their first differing letter gives: "wrt" vs "wrf" → t < f, "wrf" vs "er" → w < e, "er" vs "ett" → r < t, "ett" vs "rftt" → e < r. Chaining these gives w < e < r < t < f, so the order is "wertf".
Example 2
Input: words = ["z","x"]
Output: zx
Explanation: "z" comes before "x", so z < x and the order is "zx".
Example 3
Input: words = ["z","x","z"]
Output:
Explanation: The list says z < x (from "z","x") and also x < z (from "x","z"). That is a contradiction, so no valid order exists and the answer is "".
Compare adjacent words to extract character ordering constraints, then topological sort.
Run checks all cases above. Submit evaluates all test cases.