269. Alien Dictionary

The trick to Alien Dictionary is realizing the sorted word list isn’t the problem — it’s the evidence. Every adjacent pair of words leaks exactly one ordering fact, and once you collect those facts into a graph, the answer is a plain topological sort. The hard part is seeing the graph at all.

The problem

You’re handed a list of words written in an alien language that uses lowercase Latin letters, and the list is already sorted by that language’s unknown alphabet. Your job is to recover an ordering of the letters that’s consistent with the list — or return "" if no such ordering exists. (Full statement on LeetCode.)

Take ["wrt", "wrf", "er"]. Comparing "wrt" and "wrf", the first two letters match and then t vs f differ — so t comes before f. Comparing "wrf" and "er", they differ at the very first letter, so w comes before e. Two facts, and you build up from there.

Intuition: adjacent words are edges, letters are nodes

Sorting is a chain of pairwise comparisons, so the only new information between two neighboring words lives at their first differing character. If word a sits right before word b, scan them together until the characters stop matching; the first mismatch a[k] != b[k] tells you a[k] precedes b[k] in the alphabet. Everything after that position tells you nothing — the sort was already decided by position k.

That single fact is a directed edge a[k] → b[k]. Do this for every adjacent pair and you have a graph over the distinct letters. A valid alphabet is any ordering where every edge points “forward” — which is exactly the definition of a topological order. If the graph has a cycle (say the words imply a < b and b < a), no linear order can satisfy both, and the answer is "".

There’s one edge case the comparison hides. If b is a prefix of a but comes after it — like "abc" before "ab" — then the words never reach a differing character, yet the ordering is impossible: a proper prefix must sort first. So a longer word appearing before its own prefix is contradictory, and you bail out with "".

With $V$ distinct letters and $E$ derived edges, both building the graph and Kahn’s BFS run in $O(V + E)$.

Solution

Kahn’s algorithm fits cleanly: seed the queue with every letter that has no prerequisites (in-degree 0), then peel letters off, decrementing their neighbors. If you can’t emit every letter, a cycle blocked you.

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        // Every distinct letter is a node; start each with in-degree 0.
        Map<Character, List<Character>> adj = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                adj.putIfAbsent(c, new ArrayList<>());
                indegree.putIfAbsent(c, 0);
            }
        }

        // Each adjacent pair contributes one edge at its first mismatch.
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            int min = Math.min(a.length(), b.length());
            // Longer word before its own prefix is contradictory.
            if (a.length() > b.length() && a.startsWith(b)) return "";
            for (int j = 0; j < min; j++) {
                char x = a.charAt(j), y = b.charAt(j);
                if (x != y) {
                    adj.get(x).add(y);
                    indegree.put(y, indegree.get(y) + 1);
                    break; // only the first difference carries information
                }
            }
        }

        // Kahn's BFS: emit letters with no unmet prerequisites.
        Queue<Character> queue = new ArrayDeque<>();
        for (char c : indegree.keySet()) {
            if (indegree.get(c) == 0) queue.offer(c);
        }
        StringBuilder order = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            order.append(c);
            for (char next : adj.get(c)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) queue.offer(next);
            }
        }

        // Missing letters mean a cycle — no valid alphabet exists.
        return order.length() == indegree.size() ? order.toString() : "";
    }
}

The prefix check has to come before the mismatch loop, because when no character differs the loop tells you nothing — you’d silently accept an impossible list. The final length comparison is the cycle detector: any letter trapped in a cycle never reaches in-degree 0, so it never gets appended.

Complexity

Let $V$ be the number of distinct letters and $E$ the edges derived from adjacent-word comparisons. Let $C$ be the total length of all words.

Step	Time	Space
Build graph	$O(C)$	$O(V + E)$
Kahn’s BFS	$O(V + E)$	$O(V)$

Since $V \le 26$ here, the graph is tiny; the input length $C$ dominates the scan, and the whole thing is effectively linear in the input.

In an interview

Say the reframe out loud before you touch code: “the sorted list is a set of pairwise constraints, so I’ll build a graph over the letters and topologically sort it.” That one sentence signals you recognized the pattern, which is most of the grade on a hard graph problem.

Then name the two traps unprompted, because interviewers plant both. First, only the first differing character between two words is a real edge — comparing the rest invents constraints that aren’t there. Second, the prefix case: ["abc", "ab"] has no differing character but is still invalid, and forgetting the check is the classic silent bug. Finish by explaining how the length comparison catches cycles, so your solution returns "" on contradictory input instead of a partial string.

This is the graph-modeling muscle the whole advanced graph patterns hub is built on — once you can spot “hidden DAG, then topological sort,” dependency-resolution problems stop looking different from each other.

References

• LeetCode 269 — Alien Dictionary