Alien Dictionary

Words from an alien language are sorted by its unknown alphabet. Return one valid ordering of its letters, or "" if the order is contradictory.

A way to picture it

You find an alien dictionary and want its alphabet. Two neighbouring entries only tell you one thing: at the first letter where they differ, the upper word's letter comes first. Gather every clue, then line up the letters so no clue is broken.

How to approach it

Each adjacent pair of words gives at most one edge (first differing letter). Topologically sort the letters; a cycle — or a word before its own prefix — means no valid order.

Example

Input: {"words":["wrt","wrf","er","ett","rftt"]}. Output: "wertf".

Complexity: O(total letters) time and O(unique letters + rules) space. Each pair of words is compared once, then Kahn's algorithm runs on at most 26 letters.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.