#269 Alien Dictionary
the problem
In plain words
You get a list of words sorted in an unknown alien alphabet (lowercase English letters). Return a string of all the letters that appear, in an order consistent with the list, or "" if no order fits. Any valid answer is accepted.
in words = ["wrt","wrf","er","ett","rftt"]
out "wertf"
t<f, w<e, r<t, e<r → w, e, r, t, f.
in words = ["z","x"]
out "zx"
in words = ["z","x","z"]
out ""
z<x and x<z — a cycle.
- 1 ≤ words.length ≤ 100
- 1 ≤ words[i].length ≤ 100
- Lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTopological sort & cycle detectionCompare at the first difference
Each pair of adjacent words gives at most one rule: the first differing letters. Collect those rules as edges, then topologically sort the letters.
solutions
From brute force to optimal
Same edges stored in a boolean matrix; colour DFS gives reverse post-order and detects contradictions.
- Mark letters present.
- Add first-difference edges; prefix violation → "".
- DFS from each present white letter; back edge → "".
- Reverse the post-order string.
C = total characters to compare; DFS scans a 26-wide row per letter.
The fixed adjacency matrix — O(1) for a fixed alphabet.
class Solution { private final int[][] edge = new int[26][26]; private final boolean[] present = new boolean[26]; private final int[] color = new int[26]; // 0 white, 1 gray, 2 black public String alienOrder(String[] words) { for (String w : words) for (char c : w.toCharArray()) present[c - 'a'] = true; for (int i = 0; i + 1 < words.length; i++) { String a = words[i], b = words[i + 1]; if (a.length() > b.length() && a.startsWith(b)) return ""; for (int j = 0; j < Math.min(a.length(), b.length()); j++) { if (a.charAt(j) != b.charAt(j)) { edge[a.charAt(j) - 'a'][b.charAt(j) - 'a'] = 1; break; } } } StringBuilder post = new StringBuilder(); for (int c = 0; c < 26; c++) { if (present[c] && color[c] == 0 && !dfs(c, post)) return ""; } return post.reverse().toString(); // reverse post-order = topological order } private boolean dfs(int u, StringBuilder post) { color[u] = 1; for (int v = 0; v < 26; v++) { if (edge[u][v] == 0) continue; if (color[v] == 1) return false; // back edge → contradiction if (color[v] == 0 && !dfs(v, post)) return false; } color[u] = 2; post.append((char) ('a' + u)); return true; }}Graph of letters; in-degrees in a map; Kahn's queue outputs the alphabet.
- Register every letter that appears (in-degree 0).
- For each adjacent pair: if the first word is longer and starts with the second → "".
- Otherwise add an edge for the first differing letters (skip duplicates via a Set).
- Run Kahn; if not all letters are output → "" (cycle).
Comparing adjacent words touches each character at most twice; the graph has ≤ 26 vertices and ≤ 26² edges.
At most 26 letters and 26² edges, regardless of input size.
class Solution { 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 + 1 < words.length; i++) { String a = words[i], b = words[i + 1]; if (a.length() > b.length() && a.startsWith(b)) return ""; // "abc" before "ab": impossible for (int j = 0; j < Math.min(a.length(), b.length()); j++) { char x = a.charAt(j), y = b.charAt(j); if (x != y) { if (adj.get(x).add(y)) indegree.merge(y, 1, Integer::sum); // skip duplicate edges break; // only the FIRST difference tells us anything } } } Deque<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)) { if (indegree.merge(next, -1, Integer::sum) == 0) queue.offer(next); } } return order.length() == indegree.size() ? order.toString() : ""; // cycle → "" }}Dry run: word pairs → rules → Kahn
in the room
How to say it in the interview
talk track
- First solve the warm-up out loud: how do I compare two words? First difference, else prefix rule.
- Each adjacent pair gives one edge — don't compare beyond the first difference.
- Call out the two "invalid" cases: prefix violation and cycle.
- Include letters that never appear in any rule — they still belong in the output.
traps
- Adding edges for letters after the first difference — those letters tell you nothing.
- Missing the ["abc", "ab"] case, which is invalid even though there is no edge.
- Adding a duplicate edge twice to in-degree but once to adjacency → a letter is never freed.
what they ask next
Follow-ups
Return the smallest such alphabet?
Use a PriorityQueue<Character> in Kahn.
before you submit
Edge cases to test
- ["abc", "ab"] → "" (a word placed before its own prefix).
- Rules that chase each other, like ["z", "x", "z"] → "".
- Letters that appear in no rule still belong in the answer.
- A single word → its letters in any order.
practise next
Similar problems
- #953Verifying an Alien DictionaryEasyin Topo Sort
- #210Course Schedule IIMediumin Topo Sort