A new language uses the lowercase English letters but in an unknown order. You are given words, a list of words sorted according to this alien alphabet. Derive the order of the letters: return them as a string in the language's order. If several are valid, return the lexicographically smallest (by normal English order). If the input is inconsistent (a contradiction, or a word appearing before its own prefix), return an empty string.
Input: words = ["baa","abcd","abca","cab","cad"] Output: "bdac" Adjacent comparisons force b<d<a<c.
Input: words = ["abc","ab"] Output: "" A word can't come before its own prefix — invalid.
- 1 <= words.length <= 100 - 1 <= words[i].length <= 100 - words consist of lowercase letters
Sorted words leak ordering information: comparing adjacent words, the first position where they differ tells you one letter comes before another (a → b). Collect all such constraints into a directed graph over the appearing letters, then topologically sort it — that's the alphabet.
Two edge cases must return "": a cycle in the constraints (contradiction), and a word that comes before its own prefix (e.g. "abc" before "ab" — impossible in any sorted order). When several letters are simultaneously free (in-degree 0), emit the smallest for the lexicographically smallest order. O(total characters).
“Which letters are in the alphabet?”
Exactly those appearing in the words.
“When is the answer empty?”
On a contradiction (cycle) or a word before its own prefix.
Each adjacent pair of words gives one edge from their first differing letters; I topologically sort those constraints.
A cycle or a longer-word-before-its-prefix means the input is invalid — return empty.
Worked example — words = ["baa","abcd","abca","cab","cad"]
baa vs abcd: b before a abcd vs abca: d before a abca vs cab: a before c cab vs cad: b before d topological order -> "bdac"
It yields exactly one edge.
A longer word before its own prefix is impossible.
Contradictory constraints have no ordering.
| Smallest-zero scan | Kahn's + min-heap | |
|---|---|---|
| Pick next letter | scan letters for smallest free one | pop the heap |
| Time | O(A² + C) | O((A + C) log A) |
| Order | lexicographically smallest | lexicographically smallest |
Both build the same constraint graph and topologically sort it (A = distinct letters, C = total characters). Full code is in the Approaches selector below.
Key takeaway
Compare adjacent words for the first differing letter to get precedence edges; topologically sort them (smallest-first). Return "" on a cycle or a word-before-its-prefix. O(total characters).
for each adjacent pair: first diff (a,b) -> edge a->b (or invalid if prefix rule broken) topological sort letters, smallest first; cycle -> ""
