aliendOrder

/**
 * 1. Treat each character as a graph node.
 * 2. Compare adjacent words.
 * 3. First differing character creates a dependency:
      c < a
   => c -> a
 * 4. Build graph + indegree.
 * 5. Run Kahn's Topological Sort.
 * 6. Handle:
   - invalid prefix case
   - cycles
 * 7. If all nodes are processed,
   return the ordering.
 */
export default function alienOrder(words) {
  const graph = new Map();
  const indegree = new Map();

  // Add every unique character
  for (const word of words) {
    for (const ch of word) {
      if (!graph.has(ch)) graph.set(ch, new Set());
      if (!indegree.has(ch)) indegree.set(ch, 0);
    }
  }

  // Build ordering rules from adjacent words
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i];
    const w2 = words[i + 1];

    // Invalid prefix case: "abc" before "ab"
    if (w1.length > w2.length && w1.startsWith(w2)) {
      return "";
    }

    const len = Math.min(w1.length, w2.length);

    for (let j = 0; j < len; j++) {
      const a = w1[j];
      const b = w2[j];

      if (a !== b) {
        if (!graph.get(a).has(b)) {
          graph.get(a).add(b);
          indegree.set(b, indegree.get(b) + 1);
        }
        break;
      }
    }
  }

  // Topological sort
  const queue = [];

  for (const [ch, degree] of indegree) {
    if (degree === 0) queue.push(ch);
  }

  let result = "";

  while (queue.length > 0) {
    const ch = queue.shift();
    result += ch;

    for (const next of graph.get(ch)) {
      indegree.set(next, indegree.get(next) - 1);

      if (indegree.get(next) === 0) {
        queue.push(next);
      }
    }
  }

  // Cycle exists
  return result.length === indegree.size ? result : "";
}