Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Alien Dictionary

Problem (restated)

Words sorted in an alien alphabet. Derive a valid letter order. Invalid prefix case → “”. Any valid topo order is acceptable when multiple exist.

Intuition

Compare consecutive words; first differing chars give precedence edge a→b (a before b). Kahn BFS for order; cycle → “”.

Approaches

Kahn order from sorted pairs

Unverified

Time O(C + E)Space O(C + E)

Idea. Build graph of unique letters. Reject if longer word is prefix of shorter while listed first. Topo sort remaining.

Walkthrough. [“wrt”,“wrf”,“er”,“ett”,“rftt”] → “wertf”.

Trade-offs. Multiple valid orders exist; tests accept any correct total order or a fixed deterministic one.

Solution

export function alienOrder(words: string[]): string {
  const chars = new Set<string>();
  for (const w of words) for (const c of w) chars.add(c);
  const g = new Map<string, Set<string>>();
  const indeg = new Map<string, number>();
  for (const c of chars) {
    g.set(c, new Set());
    indeg.set(c, 0);
  }
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i]!, b = words[i + 1]!;
    let j = 0;
    while (j < a.length && j < b.length && a[j] === b[j]) j++;
    if (j === b.length && a.length > b.length) return "";
    if (j < a.length && j < b.length && !g.get(a[j]!)!.has(b[j]!)) {
      g.get(a[j]!)!.add(b[j]!);
      indeg.set(b[j]!, indeg.get(b[j]!)! + 1);
    }
  }
  const q = [...chars].filter((c) => indeg.get(c) === 0).sort();
  const res: string[] = [];
  while (q.length) {
    const u = q.shift()!;
    res.push(u);
    for (const v of [...g.get(u)!].sort()) {
      indeg.set(v, indeg.get(v)! - 1);
      if (indeg.get(v) === 0) q.push(v);
    }
  }
  return res.length === chars.size ? res.join("") : "";
}

export function alienOrder(words: string[]): string {
  const chars = new Set<string>();
  for (const w of words) for (const c of w) chars.add(c);
  const g = new Map<string, Set<string>>();
  const indeg = new Map<string, number>();
  for (const c of chars) {
    g.set(c, new Set());
    indeg.set(c, 0);
  }
  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i]!, b = words[i + 1]!;
    let j = 0;
    while (j < a.length && j < b.length && a[j] === b[j]) j++;
    if (j === b.length && a.length > b.length) return "";
    if (j < a.length && j < b.length && !g.get(a[j]!)!.has(b[j]!)) {
      g.get(a[j]!)!.add(b[j]!);
      indeg.set(b[j]!, indeg.get(b[j]!)! + 1);
    }
  }
  const q = [...chars].filter((c) => indeg.get(c) === 0).sort();
  const res: string[] = [];
  while (q.length) {
    const u = q.shift()!;
    res.push(u);
    for (const v of [...g.get(u)!].sort()) {
      indeg.set(v, indeg.get(v)! - 1);
      if (indeg.get(v) === 0) q.push(v);
    }
  }
  return res.length === chars.size ? res.join("") : "";
}

Template connection

Topological sort from precedence constraints.

Reflection

In two consecutive words, the first letter that differs is an edge: the earlier word’s letter comes first. abc then ab is invalid, because the shorter word is a prefix and is listed second.
Kahn writes the letter order. A cycle answers the empty string. The output holds only letters that appeared.
One word produces no edge. Two equal words produce no edge.