Alien Dictionary

Problem in Plain English

Sorted alien words reveal which letter precedes which other letter. Rebuild the full letter order from those clues, or return an empty string when the clues contradict each other.

Problem Statement

You are given a list of strings words from an alien dictionary, sorted lexicographically by the rules of that language. Return each observed letter exactly once in alphabet order. Any valid order is accepted when multiple orders are possible.

Lexicographic comparison uses the first differing characters; if one word is a prefix of another, the shorter word comes first. Return an empty string when the clues contradict each other or a longer word wrongly precedes its own prefix.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] holds only lowercase English letters.

Examples

Example 1

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

Adjacent pairs give t before f, w before e, r before t, and e before r, chaining into w to e to r to t to f.

Example 2

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

The single differing pair puts z before x.

Example 3

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

The clues demand z before x and x before z, which is a cycle, so no order exists.

Example 4

Input: words = ["abc","ab"]
Output: ""

No alphabet can put a longer word before its exact prefix. Reject this even though no character differs and no edge is added.

Example 5

Input: words = ["aba"]
Output: "ab" (one valid order)

A single word imposes no precedence rules. Both ab and ba are valid, but each observed letter appears only once despite the repeated a.

Intuition

Compare adjacent words at their first mismatch: wrt and wrf say t must precede f, regardless of later characters. Represent that clue as the directed edge t -> f. Example 1 also reveals w -> e, r -> t and e -> r, making w -> e -> r -> t -> f. An alphabet satisfying every edge is a topological order. Include letters with no edges too, reject a longer word before its own prefix, and detect cycles because no letter in a cycle can come before all the others.

Approaches

DFS Postorder Topo Sort

Solution Details

Reveal DFS Postorder Topo Sort: intuition, complexity, and code

Intuition

Each letter rule is a directed edge, so the alphabet is a topological ordering of that graph. A depth-first search that records each letter only after all of its successors are recorded produces the reverse alphabet, and meeting a letter already on the current path exposes a contradiction.

Step-by-Step Logic

Initialize a vertex for every observed letter. Compare adjacent words up to their first mismatch and add that edge; reject a longer-before-prefix pair. Example 1 gives t -> f from wrt/wrf, w -> e from wrf/er, r -> t from er/ett, and e -> r from ett/rftt.
Enter w: follow w -> e -> r -> t -> f, marking each letter as on the current path.
Reach f with no outgoing edges, record f, then unwind recording t, r, e, and finally w.
Reverse the recording [f, t, r, e, w] into [w, e, r, t, f].
Return the joined string "wertf".

Why It Works

Only the first mismatch decides an adjacent comparison; later positions impose no rule. Satisfying all adjacent comparisons sorts the list by transitivity, provided the prefix rule holds. DFS marks a letter active until its successors finish: an edge to an active ancestor closes a directed cycle, making an alphabet impossible. In an acyclic graph every edge u -> v finishes v before u. Reversing finish order puts u before v for every rule. Starting from every observed letter includes disconnected and unconstrained letters, while completed marks prevent duplicate output.

Dry Run

DFS Postorder Topo Sort: variable states at each step
Operation	Active (state 1)	Finished (state 2)	Postorder
enter w	w	none	[]
follow w -> e, enter e	w,e	none	[]
follow e -> r, enter r	w,e,r	none	[]
follow r -> t, enter t	w,e,r,t	none	[]
follow t -> f, enter f	w,e,r,t,f	none	[]
finish f	w,e,r,t	f	[f]
finish t	w,e,r	f,t	[f,t]
finish r	w,e	f,t,r	[f,t,r]
finish e	w	f,t,r,e	[f,t,r,e]
finish w	none	f,t,r,e,w	[f,t,r,e,w]
other roots already finished	none	all five	unchanged
reverse and join	none	all five	return wertf

Complexity Analysis

Time Complexity

O(C)

Space Complexity

O(1)

Let C be total input characters, V distinct letters and E distinct rules. Character registration and adjacent comparisons cost O(C): each word participates in at most two comparisons. DFS costs O(V + E). With V <= 26 and E <= V(V - 1), time simplifies to O(C), using expected hash operations. Graph, states, recursion and output use O(V + E) space, or O(1) for this fixed alphabet. Java charAt traversal avoids word-sized temporary arrays; Python startswith avoids prefix slices. The trace chooses w first; different map iteration orders can visit roots differently and still return a valid alphabet.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public String alienOrder(String[] words) {5        Map<Character, Set<Character>> adj = new HashMap<>();6        for (String w : words) {7            for (int j = 0; j < w.length(); j++) {8                char c = w.charAt(j);9                adj.putIfAbsent(c, new HashSet<>());10            }11        }12        for (int i = 0; i + 1 < words.length; i++) {13            String a = words[i];14            String b = words[i + 1];15            int m = Math.min(a.length(), b.length());16            if (a.length() > b.length() && a.startsWith(b)) {17                return "";18            }19            for (int j = 0; j < m; j++) {20                if (a.charAt(j) != b.charAt(j)) {21                    // Only the first mismatch supplies a precedence rule.22                    adj.get(a.charAt(j)).add(b.charAt(j));23                    break;24                }25            }26        }27        Map<Character, Integer> state = new HashMap<>();28        StringBuilder sb = new StringBuilder();29        for (char c : adj.keySet()) {30            if (hasCycle(c, adj, state, sb)) {31                return "";32            }33        }34        return sb.reverse().toString();35    }36
37    private boolean hasCycle(char c, Map<Character, Set<Character>> adj, Map<Character, Integer> state, StringBuilder sb) {38        // State 1 means an ancestor on the active path; revisiting it closes a cycle.39        if (state.getOrDefault(c, 0) == 1) {40            return true;41        }42        if (state.getOrDefault(c, 0) == 2) {43            return false;44        }45        state.put(c, 1);46        for (char nei : adj.get(c)) {47            if (hasCycle(nei, adj, state, sb)) {48                return true;49            }50        }51        state.put(c, 2);52        // Finish successors first; reversing puts each predecessor before them.53        sb.append(c);54        return false;55    }56}

Hints

Hint 1

Only the first differing letters of neighbouring words reveal an order rule, so compare each adjacent pair once.

Hint 2

Those rules form a directed graph over the letters, which calls for an ordering algorithm rather than sorting.

Hint 3

Count incoming rules per letter, emit letters with none left, and report failure if any letter never becomes free.

Edge Cases

A longer word placed before its own prefix, such as ["abc","ab"], which is invalid on sight and returns "".
Cyclic rules such as ["z","x","z"], where no letter ever runs out of predecessors.
Letters that never appear in any rule, which start free and may sit anywhere valid in the answer.
Identical words, such as ["aa","aa"], add no edge; return the observed letter a once.
Repeated clues, such as ["za","zb","ca","cb"], include a -> b twice but count it only once.
A valid prefix pair such as ["ab","abc"] adds no edge; all three letters still belong in the answer.

Common Mistakes and Interview Tips

Missing the longer-before-prefix check, which wrongly builds rules for a dictionary that is already invalid.
Adding a duplicate rule twice and double-counting indegrees, which strands a letter that should have been freed.
Omitting rule-free letters from the graph, which drops them from the returned alphabet.
Adding an edge for every mismatch: ["ab","ba"] constrains only a -> b; adding b -> a invents a cycle.
Treating a completed DFS letter as active reports false cycles; distinguish unvisited, active and finished states.
Interview tip: explain the prefix rejection separately from cycle detection, and accept any valid alphabet rather than requiring English alphabetical order.

Key Takeaway

Pairwise precedence clues become directed edges, and peeling off predecessor-free nodes yields the global order or exposes the contradiction.