Alien Dictionary
The problem
Given nonempty words sorted under an unknown character order, return any ordering of all observed characters consistent with that sort. Return an empty string if no valid ordering exists.
Example
["za", "zb", "ca", "cb"] implies a before b and z before c; "abzc" is valid.
Need a hint?
Only the first differing character in adjacent words establishes an ordering edge.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Compare adjacent words, adding one edge at their first mismatch. Reject a longer word preceding its exact prefix. Deduplicate edges before counting indegrees. Topologically sort all observed characters, including isolated ones; a cycle prevents consuming them all.
Complexity
O(total input characters + V + E) time and O(V + E) auxiliary space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.