Topo on characters

Before you start

• Topological order / cycle

  Once the letter graph is built, this is Course Schedule with letters for courses.

  Open lesson

Why it matters

Imported dictionaries, build logs, and observed workflows may reveal relative order without providing the underlying rules. Guessing an order from all permutations becomes impossible as symbols grow, and contradictory evidence must not produce a plausible-looking answer. The result must satisfy every neighboring comparison or return empty for an invalid prefix or cycle.

words is sorted in an unknown alien alphabet. Return the smallest lexicographic string of unique letters that could be the alphabet. If the order is invalid, return "". If several valid orders exist, return the lexicographically smallest.

Input

words = ["wrt", "wrf", "er", "ett", "rftt"]

Output

"wertf"

Trying all 5! orders of w, e, r, t, and f ignores the evidence structure. The neighboring words yield t → f, w → e, r → t, and e → r; ordering those constraints produces "wertf" directly.

For ["wrt", "wrf", "er", "ett", "rftt"], neighboring pairs give t → f, w → e, r → t, and e → r from their first differing letters. Later differences carry no information. A longer word before its exact prefix would return "" immediately.

The edges form w → e → r → t → f. Only w begins with in-degree 0; removing it frees e, then r, t, and f, producing "wertf". If a cycle kept any letter above in-degree 0, the result would contain too few letters and return "".