The problem. An alien language uses lowercase English letters in an unknown order. You're given a list of words that is sorted by that order, the way a dictionary is. Return a string of all the letters that appear, in an order consistent with the list. If several orders work, return any. If the list can't be sorted by any order, return "".
words = ["wrt","wrf","er","ett","rftt"] -> "wertf"
words = ["z","x"] -> "zx"
words = ["z","x","z"] -> "" (z before x, and x before z)
words = ["abc","ab"] -> "" (a word can't come after its own prefix)This is Course Schedule with letters — the hard part is finding the arrows. Compare each word with the next one. Walk along both until the first position where they differ: there, the letter in the first word comes before the letter in the second. That is the only clue the pair gives: letters after the first difference say nothing, because the words were already decided there.
Two traps. First, if a word is followed by its own prefix ("abc" then "ab"), no alphabet can sort them — the shorter word always comes first — so return "". Second, the clues can contradict each other in a cycle (z before x before z). The topological sort catches that: some letters never become ready.
Only neighbouring pairs need comparing. If a comes before b and b before c, the clue between a and c follows from the other two.
Every letter that appears is a vertex, even one that never shows up in a clue — it still belongs in the answer. Add an arrow per clue (skip repeats, so in-degrees stay right), then take letters with no arrows coming in, exactly like ready courses.
First the word pairs give the arrows, then letters are placed as they become ready. Try the contradiction and the prefix trap.
function alienOrder(words) { const next = new Map(); // letter -> letters that come after it const indegree = new Map(); // letter -> how many letters must come first for (const word of words) { for (const ch of word) { if (!next.has(ch)) { next.set(ch, new Set()); indegree.set(ch, 0); } } } for (let i = 0; i + 1 < words.length; i++) { const a = words[i], b = words[i + 1]; if (a.length > b.length && a.startsWith(b)) return ""; // "abc" before "ab": impossible for (let j = 0; j < Math.min(a.length, b.length); j++) { if (a[j] !== b[j]) { // the first difference is the only clue if (!next.get(a[j]).has(b[j])) { next.get(a[j]).add(b[j]); // a[j] comes before b[j] indegree.set(b[j], indegree.get(b[j]) + 1); } break; } } } const queue = [...indegree.keys()].filter((ch) => indegree.get(ch) === 0); let order = ""; for (let head = 0; head < queue.length; head++) { const ch = queue[head]; order += ch; for (const after of next.get(ch)) { indegree.set(after, indegree.get(after) - 1); if (indegree.get(after) === 0) queue.push(after); } } return order.length === next.size ? order : ""; // letters left over sit on a cycle}Time O(C), space O(1). C is the total number of characters in all the words: building the graph reads each character at most twice. The graph has at most 26 letters and 26 · 25 arrows, so the sort itself and all the memory are bounded by a constant.
The same arrows, sorted with the three-state DFS from Course Schedule II: a letter finishes after every letter that must come after it, so the finishing order reversed is the alphabet. An arrow back onto the current path is a contradiction.
function alienOrder(words) { const next = new Map(); // letter -> letters that come after it for (const word of words) { for (const ch of word) { if (!next.has(ch)) next.set(ch, new Set()); } } for (let i = 0; i + 1 < words.length; i++) { const a = words[i], b = words[i + 1]; if (a.length > b.length && a.startsWith(b)) return ""; // "abc" before "ab": impossible for (let j = 0; j < Math.min(a.length, b.length); j++) { if (a[j] !== b[j]) { next.get(a[j]).add(b[j]); // a[j] comes before b[j] break; } } } const state = new Map(); // missing = new, 1 = on the current path, 2 = done const finished = []; const visit = (ch) => { if (state.get(ch) === 1) return false; // a cycle: the words contradict each other if (state.get(ch) === 2) return true; state.set(ch, 1); for (const after of next.get(ch)) { if (!visit(after)) return false; } state.set(ch, 2); finished.push(ch); // every letter after ch is already placed return true; }; for (const ch of next.keys()) { if (!visit(ch)) return ""; } return finished.reverse().join(""); // last to finish = first in the alphabet}Time O(C), space O(1). The same graph-building pass, and a DFS over at most 26 letters. The recursion is at most 26 calls deep.
Building the graph is where interviews are won or lost: one clue per neighbouring pair, from the first difference only, and the prefix check. After that, either sort works.
["abc","ab"] is impossible: return "".