Problem 24.2 · Topological SortHard

Alien Dictionary

What it teaches: Build the graph yourself from comparisons, then sort it, catching the invalid-prefix case.

Practise it on judges as “Alien Dictionary”.

The problem

words is sorted in an unknown alphabet. Return the letters in an order consistent with it, or "" if no order works. Every letter in the words must appear. When several letters are possible next, choose the one that comes first in English (making the answer unique).

Example 1

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

Example 2

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

Constraints

1 ≤ words ≤ 100
Lowercase letters

Pattern clues in the wording

→ Sorted list in an unknown order
→ Infer pairwise rules

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        return "";
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	words = ["wrt","wrf","er","ett","rftt"]	"wertf"
2	words = ["z","x"]	"zx"
3	words = ["z","x","z"]	""

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Edges from adjacent words + Kahn's · O(total characters + 26 log 26)

Edges from adjacent words + Kahn's

Time O(total characters + 26 log 26) Space O(26²)

Register every letter. For each adjacent pair, find the first difference a ≠ b and add edge a → b. Run Kahn's with a PriorityQueue. If not every letter is output, there's a cycle.

Approach 1

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indeg = new HashMap<>();
        for (String w : words)
            for (char c : w.toCharArray()) { adj.putIfAbsent(c, new HashSet<>()); indeg.putIfAbsent(c, 0); }
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            int len = Math.min(a.length(), b.length()), j = 0;
            while (j < len && a.charAt(j) == b.charAt(j)) j++;
            if (j == len) {
                if (a.length() > b.length()) return "";      // "abc" before "ab" is impossible
                continue;
            }
            if (adj.get(a.charAt(j)).add(b.charAt(j))) indeg.merge(b.charAt(j), 1, Integer::sum);
        }
        PriorityQueue<Character> ready = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> e : indeg.entrySet()) if (e.getValue() == 0) ready.offer(e.getKey());
        StringBuilder sb = new StringBuilder();
        while (!ready.isEmpty()) {
            char c = ready.poll();
            sb.append(c);
            for (char d : adj.get(c)) if (indeg.merge(d, -1, Integer::sum) == 0) ready.offer(d);
        }
        return sb.length() == indeg.size() ? sb.toString() : "";
    }
}

Verdict: Only adjacent pairs are needed; others follow transitively.

Before you submit

Edge cases and common mistakes

Test these inputs

One word
Prefix ordering violation
Contradicting pairs (cycle)

Mistakes people make

Comparing letters beyond the first difference.
Adding the same edge twice and double-counting in-degree.

Interview

Follow-up questions

Why only adjacent pairs?

Command Palette

The problem

Approaches

Edges from adjacent words + Kahn's

Edge cases and common mistakes

Follow-up questions