Alien Dictionary

Problem

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language. Return a string of the unique letters in the new alien language sorted in ascending order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

Examples

The brute-force approach

Try every permutation of the unique letters and check if it's consistent with all observed orderings. Return the first valid permutation.

for perm in permutations(unique_letters):
    if consistent(perm, edges):
        return ''.join(perm)
return ""

O(n! × edges) where n is the number of unique letters. Combinatorial explosion. Topological sort solves the same problem in O(V + E).

Spotting the pattern

This is a Topological Sort problem. The key question to ask yourself:

When you compare two adjacent words and find the first differing character, what does that tell you about the alphabet order?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.