DSA problem
Alien Dictionary
There is a new alien language that uses the lowercase English letters but with an unknown ordering between them. You are given a list of strings words from this language, sorted lexicographically by the rules of that language. Derive any string of the unique letters in the new language sorted by the alien lexicographic rules. If there is no such ordering (the input contradicts itself), return "".
If two adjacent words w1 and w2 in the input agree on every position up to some index k, then in the alien alphabet w1[k] < w2[k] must hold. That single inequality is the only character-level ordering information we can extract from any pair — the rest of the characters tell us nothing. Walk all adjacent pairs and collect these inequalities; together they define a directed graph whose nodes are letters and whose edges are the constraints a → b meaning "a precedes b".
The valid alien orderings of the letters are exactly the topological orderings of this graph. Use Kahn's BFS: compute in-degrees, push every zero-in-degree letter, and pop in order. Each popped letter is appended to the result. If a cycle exists we cannot consume every letter and the input is inconsistent.
There is also an invalid edge case to detect explicitly: if w1 is a strict prefix of w2 (e.g. abc then ab), no character pair contradicts the order, yet the dictionary order itself is impossible — return "". With those rules the algorithm runs in O(C) where C is the total length of all words.
Examples
words = ["wrt","wrf","er","ett","rftt"]"wertf"words = ["z","x"]"zx"words = ["z","x","z"]""Constraints
- 1 <= words.length <= 100
- 1 <= words[i].length <= 100
- words[i] consists of only lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.