Alien Dictionary

The problem

Implement `foreignDictionary(words)`, given words already sorted according to an unknown alien alphabet. Return one valid ordering of the letters that appear, as a string, or `""` if no ordering is consistent with the given sequence.

`words = ["hrn","hrf","er","enn","rfnn"]` returns `"hernf"` — each adjacent pair contributes one constraint (`n < f`, `h < e`, `r < n`, `e < r`), and any full ordering consistent with all four is accepted. `words = ["abc","ab"]` returns `""` — `"ab"` is a prefix of `"abc"` but appears after it, which no alphabet could make lexicographically valid.

The approach

The traversal is exactly `courseScheduleII`'s Kahn's algorithm, unchanged: an `inDegree` count per letter, a queue seeded with every letter already at `inDegree === 0`, and `order` built by pushing whatever gets dequeued. `prerequisites` handed that problem an edges array directly; here the edges have to be inferred from word order first, which is the only genuinely new step.

Only adjacent words are ever compared — `words[i]` against `words[i + 1]` — and only the first letter where they differ produces a constraint. That's the one letter that actually decided their relative order; everything after it in either word played no part in why `words[i]` sorted before `words[i + 1]`.

The prefix case has to be checked before comparing any letters at all: if `words[i]` is longer than `words[i + 1]` and they agree on every letter `words[i + 1]` has, then `words[i + 1]` is a prefix of `words[i]` — a shorter prefix always sorts first by the rules given, so `words[i]` appearing before it is a contradiction, and the function returns `""` immediately rather than feeding a broken constraint into the graph.

Each edge is only ever added once — `adj[first[j]].has(second[j])` guards the `add`/`inDegree++` — since the same letter pair can be re-derived from more than one word comparison, and double-counting it would leave that letter's `inDegree` one too high, permanently short of `0` and never queued even though the constraint was satisfied the first time it appeared. The remaining cycle check is the same gap-detection as `courseSchedule`/`courseScheduleII`: `order.length` short of the total letter count means some letters are stuck in a cycle and never reached `inDegree === 0`.

The solution

class Solution {
    /**
     * @param {string[]} words
     * @returns {string}
     */
    foreignDictionary(words) {
        const adj = {};
        const inDegree = {};

        for (const word of words) {
            for (const ch of word) {
                if (!(ch in adj)) {
                    adj[ch] = new Set();
                    inDegree[ch] = 0;
                }
            }
        }

        for (let i = 0; i < words.length - 1; i++) {
            const first = words[i];
            const second = words[i + 1];
            const minLen = Math.min(first.length, second.length);

            if (first.length > second.length && first.slice(0, minLen) === second.slice(0, minLen)) {
                return "";
            }

            for (let j = 0; j < minLen; j++) {
                if (first[j] !== second[j]) {
                    if (!adj[first[j]].has(second[j])) {
                        adj[first[j]].add(second[j]);
                        inDegree[second[j]]++;
                    }
                    break;
                }
            }
        }

        const q = [];
        for (const ch in inDegree) {
            if (inDegree[ch] === 0) q.push(ch);
        }

        const order = [];
        while (q.length) {
            const ch = q.shift();
            order.push(ch);

            for (const next of adj[ch]) {
                inDegree[next]--;
                if (inDegree[next] === 0) q.push(next);
            }
        }

        return order.length === Object.keys(inDegree).length ? order.join("") : "";
    }
}

Time O(N * L)Space O(1)