How do you approach Alien Dictionary?

Compare adjacent words to find character ordering constraints.

What is the time complexity of Alien Dictionary?

Time complexity: O(C) where C is the total number of characters in all words. Space complexity: O(U) where U is the number of unique characters.

What are common mistakes on Alien Dictionary?

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question. Building the edges the wrong way round - prerequisite pairs are the classic reversal. Seeding the queue with every node instead of only those with zero indegree.

Sitelet https://gitgood.dev/coding/alien-dictionary

gitGood.dev

← Back to problems

Alien Dictionary

HardAlgorithms

Description

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings are sorted lexicographically by the rules of this new language.

Derive the order of letters in this language. If no valid ordering exists, return an empty string. If there are multiple valid orderings, return the lexicographically smallest one.

Note: If a longer word appears before a shorter word that is its prefix (e.g., "abc" before "ab"), the input is invalid and you should return an empty string.

Example 1

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

Output: "wertf"

Explanation: From the input: w < e, r < t, t < f, e < r. So the order is w, e, r, t, f.

Example 2

Input: words = ["z","x"]

Output: "zx"

Example 3

Input: words = ["z","x","z"]

Output: ""

Explanation: The order is invalid because z cannot be both before and after x.

Constraints

- 1 <= words.length <= 100 - 1 <= words[i].length <= 100 - words[i] consists of only lowercase English letters.

Alien Dictionary: approach, complexity and pitfalls

A hard topological sort problem, graded against 6 test cases (3 of them hidden).

The pattern: Topological Sort

Ordering a directed acyclic graph so every dependency comes first.

Reach for it when you see: Prerequisites, build order, task scheduling, or "can this be completed?"

If you are stuck

Show the 3-step hint ladder

Compare adjacent words to find character ordering constraints.
Build a directed graph from these constraints, then perform topological sort.
Use BFS (Kahn's algorithm) for topological sort. If the result has fewer characters than expected, there is a cycle.

The optimal approach

Show the approach: Topological Sort (BFS)

Build a graph by comparing adjacent words character by character. The first differing character gives an ordering edge. Use Kahn's algorithm (BFS with in-degree tracking) for topological sort. To get the lexicographically smallest order, use a sorted queue (min-heap). If the result has fewer characters than total unique characters, there is a cycle.

Time: O(C) where C is the total number of characters in all words
Space: O(U) where U is the number of unique characters

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Topological Sort mistakes

These apply to the pattern as a whole, not just this problem.

Not detecting the cycle. If fewer nodes come out than went in there is no valid ordering, and that is usually the real question.
Building the edges the wrong way round - prerequisite pairs are the classic reversal.
Seeding the queue with every node instead of only those with zero indegree.