w, r, t, f, e
chars
Given a sorted list of alien-language words, reconstruct the ordering of the alien alphabet by reading edges from the first differing character in every adjacent pair, then running Kahn's BFS topological sort to linearise those constraints — returning "" if a cycle or prefix violation makes the ordering impossible.
You receive a list of words sorted in an alien language. Use the sorted order to infer which letters come before others, then output the full alien alphabet. Example: ["wrt", "wrf", "er", "ett", "rftt"] → "wertf". Return "" if the ordering is contradictory (cycle) or a longer word illegally precedes a prefix (e.g. "abc" before "ab").
word[i][j] < word[i+1][j] in the alien alphabet. All later characters are uninformative. Collect these constraints as directed edges, then run a topological sort. If there is a cycle, no valid ordering exists.adj and indegree maps. Characters not in any word cannot appear in the answer.(words[i], words[i+1]), scan positions left to right and stop at the first mismatch. That gives edge a[j] → b[j]. Ignore all subsequent characters — they carry no ordering information about this pair.words[i] is longer than words[i+1] and is a prefix of it, the input violates sorted order — return "" immediately."".Edge derivation is O(W·L) where W is the number of words and L is the average word length. The BFS itself is O(V + E) where V ≤ 26 and E ≤ V² ≤ 676. In practice the bottleneck is reading the words.
wrt, wrf, er, ett, rftt. Collecting all characters and initialising adjacency/indegree maps.function alienOrder(words: string[]): string {
// 1. Collect every character; initialise maps
const adj = new Map<string, Set<string>>();
const indegree = new Map<string, number>();
for (const w of words)
for (const c of w)
if (!adj.has(c)) { adj.set(c, new Set()); indegree.set(c, 0); }
// 2. Derive ordering edges from adjacent word pairs
for (let i = 0; i < words.length - 1; i++) {
const a = words[i], b = words[i + 1];
const minLen = Math.min(a.length, b.length);
let found = false;
for (let j = 0; j < minLen; j++) {
if (a[j] !== b[j]) { // ONLY the first differing char gives an edge
if (!adj.get(a[j])!.has(b[j])) {
adj.get(a[j])!.add(b[j]);
indegree.set(b[j], indegree.get(b[j])! + 1);
}
found = true;
break; // stop — later chars tell us nothing
}
}
// Prefix edge case: "abc" before "ab" is impossible
if (!found && a.length > b.length) return '';
}
// 3. Kahn's BFS topological sort
const queue: string[] = [];
for (const [c, deg] of indegree)
if (deg === 0) queue.push(c);
let result = '';
while (queue.length) {
const cur = queue.shift()!;
result += cur;
for (const nb of adj.get(cur)!) {
const newDeg = indegree.get(nb)! - 1;
indegree.set(nb, newDeg);
if (newDeg === 0) queue.push(nb);
}
}
// 4. Cycle ⇒ not all chars reached
return result.length === indegree.size ? result : '';
}adj and indegree. Using if (!adj.has(c)) avoids reinitialising characters seen earlier.for loop stops at the first mismatch and adds exactly one directed edge. The break is critical — it prevents false edges from later positions. The prefix check on line 25 catches the "abc" before "ab" case before it can silently corrupt the sort.result, decrement every neighbour's indegree. A neighbour hitting zero means all its predecessors are already placed — safe to enqueue. The order within tied-indegree characters is arbitrary (any valid topo order is accepted).result.length < indegree.size some characters were never dequeued — they form a cycle. Return ""."".| "reconstruct order from sorted examples" | edge-per-adjacent-pair + topo sort |
| "first differing position" | break after adding edge — later positions ignored |
| "longer word before its own prefix" | return "" immediately (invalid) |
| "cycle in ordering constraints" | Kahn's BFS count < total chars → return "" |
// 1. init adj + indegree for every unique char
// 2. compare adjacent pairs → first diff char → edge u→v
// if a is prefix of b but longer → return ''
// 3. Kahn's BFS:
const queue = [...chars with indegree 0];
let result = '';
while (queue.length) {
const cur = queue.shift()!;
result += cur;
for (const nb of adj.get(cur)!) {
if (--indegree[nb] === 0) queue.push(nb);
}
}
// 4. cycle check
return result.length === totalChars ? result : '';["wrt", "wrf"], which edge is derived and why?