Alien Dictionary

1. Problem & Core Objective

Given a list of words from an alien language, sorted lexicographically by that language's unknown alphabet order, derive an ordering of its letters. If several are valid, return any; if none is, return "".

words = ["wrt","wrf","er","ett","rftt"]   →  "wertf"
words = ["z","x"]                         →  "zx"
words = ["z","x","z"]                     →  ""      (contradiction)

Constraints: 1 <= words.length <= 100 · 1 <= word.length <= 100 · lowercase letters

What's actually being tested: extracting a graph from an ordering, then topological-sorting it. Two specific traps make this Hard: only the first differing character of an adjacent pair tells you anything, and a prefix violation (["abc","ab"]) is invalid regardless of the letter order.

2. First-Principles Thought Process

What the sorted order tells you

Take two adjacent words. Lexicographic comparison scans left to right and stops at the first position where they differ. That single comparison is all the information the pair carries.

"wrt" before "wrf"  →  scan: w=w, r=r, t≠f  →  t comes before f

Everything after that position is irrelevant — the comparison already terminated.

Taking more than the first difference is the most common bug. From "wrt" and "wrf" you learn only t < f, not anything about later characters.

The prefix rule

If one word is a prefix of the other, the shorter must come first. So ["abc", "ab"] is impossible in any alphabet ordering — a contradiction in the input itself, not in the derived graph.

Missing this returns a plausible ordering for invalid input.

Then it's a topological sort

Each letter is a node; each derived constraint a < b is an edge a → b. A valid alphabet order is a topological order of that graph.

A cycle means contradictory constraints — like z < x and x < z from ["z","x","z"] — so return "".

Collecting the alphabet

Only letters that actually appear may be output, and every appearing letter must appear exactly once — including letters with no constraints at all, which can go anywhere.

So initialise the node set from all characters in all words, not just those involved in edges.

3. Solution Paths

Approach 1 — Compare all pairs, not just adjacent ones (brute force)

public String alienOrder(String[] words) {
    Map<Character, Set<Character>> adj = new HashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();
    for (String w : words)
        for (char c : w.toCharArray()) {
            adj.putIfAbsent(c, new HashSet<>());
            inDegree.putIfAbsent(c, 0);
        }

    for (int i = 0; i < words.length; i++)
        for (int j = i + 1; j < words.length; j++)        // EVERY pair, not just adjacent
            if (!addConstraint(words[i], words[j], adj, inDegree)) return "";

    return topoSort(adj, inDegree);
}

• Time O(N² · L) · Space O(1) — at most 26 nodes

Counter-questions on this approach

⭐ "Does comparing non-adjacent pairs give extra information?"

No — it gives the same information, redundantly. Sortedness is transitive: if words[0] < words[1] < words[2], then words[0] < words[2] follows and adds no new constraint beyond what the adjacent pairs already encode.

So it's O(N²) comparisons where O(N) suffices. Harmless for correctness, wasteful in work.

⭐ "Is it harmless, though? Could a non-adjacent pair create a spurious edge?"

It can create duplicate edges, which is why adj uses a Set<Character> — adding t → f twice must not increment inDegree twice, or the topological sort would never release f.

That's a real trap: with a List instead of a Set, the in-degree bookkeeping breaks. The adjacent-pairs-only version has the same risk from repeated pairs, so the Set is needed either way.

"Is O(N² · L) slow at these limits?"

100² × 100 = 10^6 — fine. The objection is that it does quadratically many comparisons to derive the same constraint set that N − 1 adjacent comparisons produce.

Approach 2 — Adjacent pairs plus Kahn's topological sort (optimal)

public String alienOrder(String[] words) {
    Map<Character, Set<Character>> adj = new HashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();

    for (String w : words)                                // every appearing letter is a node
        for (char c : w.toCharArray()) {
            adj.putIfAbsent(c, new HashSet<>());
            inDegree.putIfAbsent(c, 0);
        }

    for (int i = 0; i < words.length - 1; i++) {          // ADJACENT pairs only
        String a = words[i], b = words[i + 1];

        if (a.length() > b.length() && a.startsWith(b)) return "";   // prefix violation

        for (int j = 0; j < Math.min(a.length(), b.length()); j++) {
            char ca = a.charAt(j), cb = b.charAt(j);
            if (ca != cb) {
                if (adj.get(ca).add(cb)) inDegree.merge(cb, 1, Integer::sum);
                break;                                     // FIRST difference only
            }
        }
    }

    Queue<Character> q = new ArrayDeque<>();
    for (var e : inDegree.entrySet()) if (e.getValue() == 0) q.offer(e.getKey());

    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        char c = q.poll();
        sb.append(c);
        for (char next : adj.get(c))
            if (inDegree.merge(next, -1, Integer::sum) == 0) q.offer(next);
    }

    return sb.length() == inDegree.size() ? sb.toString() : "";   // short = cycle
}

Trace — ["wrt","wrf","er","ett","rftt"]:

Nodes {w,r,t,f,e}, in-degrees w:0, e:1, r:1, t:1, f:1. Kahn's: w → releases e → releases r → releases t → releases f.

Result "wertf" ✓

• Time O(C) where C is the total characters — at most 10^4 · Space O(1) (≤ 26 nodes, ≤ 676 edges)

Counter-questions on this approach

⭐ "Why only the FIRST differing character?"

Because that's where the lexicographic comparison terminates. "wrt" < "wrf" is decided entirely at position 2 — the characters after it were never examined by the sort, so they carry no ordering information.

Deriving t < f and something from later positions would invent constraints the input doesn't support, potentially creating a false cycle and returning "" for valid input.

The break is load-bearing.

⭐ "Explain the prefix check. Why is ['abc','ab'] invalid?"

Lexicographic order puts a prefix before the string that extends it — "ab" comes before "abc" in every alphabet, because the comparison runs out of characters in the shorter word first and shortness wins.

So ["abc","ab"] is unsortable regardless of the letter order. It's a contradiction in the input, not in the derived graph, so no amount of topological sorting would catch it — it has to be checked explicitly.

Without the check you'd derive no constraint from that pair (they never differ) and return a plausible but wrong answer.

⭐ "Why Set<Character> for the adjacency rather than List?"

To prevent double-counting in-degrees. The same constraint can be derived twice — ["ab","ac","ad"] gives b→c and c→d, but a different input could repeat a pair.

With a List, adding t → f twice would increment inDegree[f] twice, and the single decrement when t is processed would leave it at 1 forever. f would never be released, the output would be short, and the function would wrongly report a cycle.

The if (adj.get(ca).add(cb)) guard makes the increment conditional on the edge being new — that's the fix.

⭐ "Why does a short output mean a cycle?"

Kahn's emits a node only when its in-degree reaches 0. If the queue empties with letters unemitted, those letters still have unmet constraints from each other — following them backwards in a finite set must repeat, which is a cycle.

A cycle means contradictory constraints, so no valid alphabet exists and the answer is "".

"Why seed the node set from all characters rather than from the edges?"

Because a letter may appear in the words without being involved in any constraint — ["a","b"] gives a → b, but a third letter appearing only inside words has in-degree 0 and no edges. It must still be in the output.

Seeding from edges would silently drop those letters.

"Is the output unique?"

Usually not. Any letter with in-degree 0 is a legal next choice, so multiple valid orders can exist and the problem accepts any. Using a PriorityQueue instead would give the lexicographically smallest.

"Could a.length() > b.length() && a.startsWith(b) be simplified?"

You could check inside the loop: if the loop completes without finding a difference and a is longer, it's a violation. That's equivalent and avoids the extra startsWith scan. Both are O(L).

Comparison

4. Why the Optimal Wins

Comparing all pairs derives the same constraints redundantly, since sortedness is transitive — O(N²) work for O(N) information.

But the real content isn't the complexity; it's the two correctness traps. Only the first difference matters, because that's where the comparison stopped. And a prefix violation is a contradiction in the input that no graph algorithm will surface.

After those, it's a standard topological sort.

The framing worth keeping:

A sorted list encodes one constraint per adjacent pair, at the first differing character — and nothing else. Build the graph from those, check the prefix rule separately, then topologically sort. A cycle means the input is contradictory.

5. Java Prerequisites

Deriving one constraint per adjacent pair

for (int j = 0; j < Math.min(a.length(), b.length()); j++)
    if (a.charAt(j) != b.charAt(j)) {
        if (adj.get(a.charAt(j)).add(b.charAt(j)))
            inDegree.merge(b.charAt(j), 1, Integer::sum);
        break;                                   // FIRST difference only
    }

Set adjacency prevents double-counting — add returns false for a duplicate edge, so the in-degree increment is conditional.

Map.merge for counter arithmetic:

inDegree.merge(c, 1, Integer::sum);        // increment
inDegree.merge(c, -1, Integer::sum);       // decrement, returns the new value

Prefix check — a.length() > b.length() && a.startsWith(b) means invalid input.

Cycle detection — output length shorter than the node count.

6. Interview Communication Guide

Clarifying questions: Are the words guaranteed sorted in the alien order (yes — that's the premise)? What should invalid input return (empty string)? If multiple orders are valid, any of them (yes)? Must every appearing letter be in the output (yes)? Lowercase only (yes, so at most 26 nodes)?

The pitch

"The sorted list is the data source. Each adjacent pair of words gives exactly one constraint, at the first position where they differ — because that's where lexicographic comparison terminates.

From 'wrt' before 'wrf', I learn t comes before f, and nothing else. The characters after that position were never examined by the sort, so deriving anything from them would invent constraints the input doesn't support — possibly creating a false cycle and rejecting valid input. The break after the first difference is load-bearing.

I only compare adjacent pairs, because sortedness is transitive — non-adjacent pairs give the same constraints redundantly.

There's a second trap: if one word is a prefix of the next and comes after it, like ['abc','ab'], the input is invalid in every alphabet, since a prefix always sorts first. That pair produces no differing character, so no graph algorithm will catch it — it has to be checked explicitly.

Then it's a topological sort. Each letter is a node, each constraint an edge, and I use Kahn's algorithm. If the output is shorter than the number of distinct letters, some letters still had unmet constraints from each other — a cycle, meaning contradictory input, so return the empty string.

Two implementation details. I seed the node set from all characters in all words, because a letter with no constraints still belongs in the output. And I use a Set for the adjacency, so a repeated constraint doesn't increment the in-degree twice — that would leave a letter permanently unreleased and falsely report a cycle.

O(total characters), with at most 26 nodes."

Edge cases to volunteer:

Name the prefix violation. It's the case with no differing character at all, so the graph is empty and a solution without the explicit check returns a plausible ordering for input that cannot exist.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the lexicographically smallest valid order."

Swap the ArrayDeque for a PriorityQueue<Character>, so the smallest available letter is always emitted first. O(C + V log V). The greedy is safe because any in-degree-0 letter is a legal choice.

⭐ "Return ALL valid orderings."

Backtracking over the set of currently-available letters — choose one, decrement, recurse, undo. Exponentially many in general, and counting them is #P-complete.

"What if the alphabet weren't limited to 26 letters?"

Nothing structural changes — the maps are already keyed by character. The O(1) space claim becomes O(V + E) in the alphabet size, and for Unicode you'd iterate code points rather than chars.

"Detect whether the input has enough information to determine a unique order."

The order is unique exactly when Kahn's queue never holds more than one letter at a time — any moment with two available letters means a genuine choice. One extra check inside the loop.

"What if some words were out of order in the input?"

That's the contradiction case, and it surfaces either as a prefix violation or as a cycle. Both already return "". Worth noting the algorithm validates the input as a side effect of deriving the answer.

"What if you had to infer the order from arbitrary comparisons, not a sorted list?"

Same graph, different extraction — each comparison a < b is an edge directly, with no first-difference logic. The topological sort is unchanged, which shows that part of the solution was never specific to strings.