Alien Dictionary

Table of Contents +

You find a dictionary from another planet. The words are written with normal letters. But the letters are not in our usual order. The words are sorted by the alien order, not ours. Your job is to figure out that secret letter order from the word list. This question hides a graph inside it. So it is a clean test of topological sort.

🎯 The Problem

You get a list of words from the alien language. Here are the rules.

  • The words are already sorted by the alien letter order.
  • You return the order of letters in that language.
  • If many valid orders exist, any one is fine.
  • If the order is impossible, return an empty string.
Input:  words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"


Explanation: Comparing neighboring words gives the rules
t before f, w before e, r before t, e before r. One valid order is wertf.

We compare each word with the next one. The first place they differ tells us one letter comes before another. Then we must arrange all letters so every rule holds. This arranging is called a topological sort. A topological sort lines up nodes so every arrow points forward, never backward. Here is the rule graph for the example.

w

e

r

t

f

🐢 Approach 1: Try Every Letter Order (Brute Force)

The idea in one line: generate every possible order of the letters and keep the first one that obeys all rules.

The idea:

  • List every possible order of the letters.
  • Check each order against all the ordering rules.
  • Return the first order that obeys them all.

How it works:

  • Read the rules by comparing neighboring words.
  • Then test orders one by one.

Why it is weak:

  • The number of orders grows enormously with more letters.
  • Testing them all is hopeless even for a small alphabet.
  • It throws away the structure the rules give us.

Here is the permutation-check code:

alien_dictionary_brute_force.py
from itertools import permutations


def alien_order(words):
    letters = sorted(set("".join(words)))
    def valid(order):
        rank = {ch: i for i, ch in enumerate(order)}
        return all([rank.get(a, -1) for a in w1] <= [rank.get(a, -1) for a in w2] for w1, w2 in zip(words, words[1:]))
    for order in permutations(letters):
        if valid(order):
            return "".join(order)
    return ""

🚀 Approach 2: Topological Sort With Kahn’s Algorithm (Best)

The idea in one line: turn the rules into a graph, then peel off letters that have nothing before them.

The idea:

  • Each letter is a node.
  • Each rule “letter a before letter b” is an arrow from a to b.
  • Run a topological sort over that graph.

How it works:

  • Kahn’s algorithm repeatedly takes nodes with no arrows pointing in.
  • The arrows pointing into a node is its in-degree.
  • A letter with in-degree zero has nothing that must come before it, so it is safe to place next.
  • Put all in-degree-zero letters into a queue.
  • Pull one out, add it to the answer, and remove its outgoing arrows.
  • Removing arrows lowers the in-degree of its targets. If a target hits zero, push it.
  • Repeat until the queue is empty.

Why it is fast:

  • Each letter and rule is touched once.
  • The alphabet is small, so the sort is tiny.

Watch for two bad cases:

  • If letters are left out, there is a cycle. A cycle means the rules contradict, like a before b and b before a. Return an empty string.
  • If a longer word comes before its own prefix, like "abc" before "ab", that is invalid. Return an empty string.

Here is how Kahn’s algorithm peels off free letters on the example. Each step removes a letter with in-degree zero.

w is free, take it

e becomes free, take it

r becomes free, take it

t becomes free, take it

f becomes free, take it

Order = wertf

Steps to Solve

  1. Collect every letter that appears. Set each letter’s in-degree to zero and give it an empty neighbor list.
  2. Compare each pair of neighboring words. Find the first letter where they differ. Add an arrow from the earlier word’s letter to the later word’s letter. Raise the target’s in-degree.
  3. If a word comes before its own prefix, return an empty string.
  4. Push all letters with in-degree zero into a queue.
  5. Pull a letter, add it to the answer, and lower the in-degree of its neighbors. Push any that reach zero.
  6. If the answer holds every letter, return it. Otherwise return an empty string.

This Python version uses a dictionary of sets for the rules and a deque as the queue.

alien.py
from collections import defaultdict, deque


def alien_order(words):
    adj = defaultdict(set)
    indeg = {c: 0 for w in words for c in w}  # every letter starts at 0


    for a, b in zip(words, words[1:]):
        min_len = min(len(a), len(b))
        k = 0
        while k < min_len and a[k] == b[k]:
            k += 1
        if k == min_len:
            if len(a) > len(b):
                return ""               # prefix came after, invalid
        elif b[k] not in adj[a[k]]:
            adj[a[k]].add(b[k])         # rule: a[k] before b[k]
            indeg[b[k]] += 1


    queue = deque([c for c in indeg if indeg[c] == 0])  # free letters
    result = []
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in adj[u]:
            indeg[v] -= 1               # remove u's outgoing arrow
            if indeg[v] == 0:
                queue.append(v)
    if len(result) != len(indeg):
        return ""                       # a cycle left letters out
    return "".join(result)




words = ["wrt", "wrf", "er", "ett", "rftt"]
print(alien_order(words))

The output of the above code will be:

wertf

Let us read the Python version line by line and see why each step is there.

adj = defaultdict(set)
indeg = {c: 0 for w in words for c in w}

adj maps each letter to the set of letters that must come after it. We use a set so a repeated rule does not get counted twice. indeg starts every letter at zero. We must include every letter that appears, even ones with no rule, or they would be lost from the answer.

for a, b in zip(words, words[1:]):

zip(words, words[1:]) pairs each word with the next one. We only learn rules by comparing neighbors, because the list is sorted. So neighboring words are where the ordering shows.

k = 0
while k < min_len and a[k] == b[k]:
    k += 1

We scan both words together until the letters differ. The first differing position is the only one that gives a rule. Everything before it is equal, so it tells us nothing.

if k == min_len:
    if len(a) > len(b):
        return ""
elif b[k] not in adj[a[k]]:
    adj[a[k]].add(b[k])
    indeg[b[k]] += 1

If we reached the end of the shorter word with no difference, and the first word is longer, that is the bad prefix case, so we stop. Otherwise we add the rule a[k] before b[k]. We raise the in-degree of b[k] because now one more letter must come before it.

queue = deque([c for c in indeg if indeg[c] == 0])
while queue:
    u = queue.popleft()
    result.append(u)
    for v in adj[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            queue.append(v)

This is Kahn’s algorithm. We start with every free letter, meaning in-degree zero. We place a letter, then remove its arrows by lowering the in-degree of each target. When a target hits zero, it becomes free, so it joins the queue.

if len(result) != len(indeg):
    return ""
return "".join(result)

If we placed fewer letters than exist, some were trapped in a cycle, so the rules contradict and we return an empty string. Otherwise we join the letters into the final order.

⏱️ Time and Space Complexity

Let C be the total number of characters across all words. Comparing neighboring words touches each character at most once, so reading the rules is O(C). There are at most 26 letters and a bounded number of rules between them. So the topological sort is small and fast. The overall time is O(C). The space holds the graph and in-degree counts, which is bounded by the alphabet, so O(1) extra beyond the input, or O(C) counting the words.

Approach Time Complexity Space Complexity
Try all letter orders Factorial O(1)
Topological sort (Kahn’s) O(C) O(1) plus the alphabet

Tip

Two cases trip people up here. A cycle in the rules means no valid order, return empty. And a longer word before its own prefix, like “abc” before “ab”, is also invalid. Mention both in an interview to show care.

🧩 Key Takeaways

  • ✅ Compare neighboring words. The first differing letter gives one ordering rule.
  • ✅ Build a graph where each rule is an arrow from the earlier letter to the later one.
  • ✅ Topological sort with Kahn’s algorithm places free letters, those with in-degree zero, first.
  • ✅ Leftover letters mean a cycle, so the rules contradict and you return an empty string.
  • ✅ A word before its own prefix is invalid, so return an empty string for that too.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Where do the ordering rules come from?

    Why: Neighboring sorted words differ first at one position, which tells you one letter comes before another.

  2. 2

    In Kahn's algorithm, which letter is safe to place next?

    Why: A letter with in-degree zero has no unmet rule, so it can be placed next.

  3. 3

    What does it mean if some letters are never placed?

    Why: Letters trapped by a cycle can never reach in-degree zero, so a valid order is impossible.

  4. 4

    Which case is also invalid besides a cycle?

    Why: If a longer word comes before its prefix, the sorting is impossible, so return an empty string.

Score: 0 / 4

🚀 What’s Next?

Previous Swim in Rising Water Next Cheapest Flights Within K Stops