Alien Dictionary

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> adj;
        unordered_map<char, int> indeg;
        for (auto& w : words) for (char c : w) indeg[c];
        for (int i = 0; i + 1 < (int)words.size(); ++i) {
            const string& a = words[i];
            const string& b = words[i + 1];
            if (a.size() > b.size() && a.substr(0, b.size()) == b) return "";
            for (int j = 0; j < (int)min(a.size(), b.size()); ++j) {
                if (a[j] != b[j]) {
                    if (adj[a[j]].insert(b[j]).second) ++indeg[b[j]];
                    break;
                }
            }
        }
        queue<char> q;
        for (auto& [c, d] : indeg) if (d == 0) q.push(c);
        string out;
        while (!q.empty()) {
            char c = q.front(); q.pop();
            out += c;
            for (char nb : adj[c]) {
                if (--indeg[nb] == 0) q.push(nb);
            }
        }
        return (int)out.size() == (int)indeg.size() ? out : "";
    }
};

func alienOrder(words []string) string {
    adj := make(map[byte]map[byte]bool)
    indeg := make(map[byte]int)
    for _, w := range words {
        for i := 0; i < len(w); i++ {
            if _, ok := indeg[w[i]]; !ok {
                indeg[w[i]] = 0
            }
        }
    }
    for i := 0; i+1 < len(words); i++ {
        a, b := words[i], words[i+1]
        if len(a) > len(b) && a[:len(b)] == b {
            return ""
        }
        lim := len(a)
        if len(b) < lim {
            lim = len(b)
        }
        for j := 0; j < lim; j++ {
            if a[j] != b[j] {
                if adj[a[j]] == nil {
                    adj[a[j]] = make(map[byte]bool)
                }
                if !adj[a[j]][b[j]] {
                    adj[a[j]][b[j]] = true
                    indeg[b[j]]++
                }
                break
            }
        }
    }
    q := []byte{}
    for c, d := range indeg {
        if d == 0 {
            q = append(q, c)
        }
    }
    out := []byte{}
    for len(q) > 0 {
        c := q[0]
        q = q[1:]
        out = append(out, c)
        for nb := range adj[c] {
            indeg[nb]--
            if indeg[nb] == 0 {
                q = append(q, nb)
            }
        }
    }
    if len(out) != len(indeg) {
        return ""
    }
    return string(out)
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj: dict[str, set[str]] = defaultdict(set)
        indeg: dict[str, int] = {c: 0 for w in words for c in w}
        for a, b in zip(words, words[1:]):
            if len(a) > len(b) and a.startswith(b):
                return ""
            for x, y in zip(a, b):
                if x != y:
                    if y not in adj[x]:
                        adj[x].add(y)
                        indeg[y] += 1
                    break
        q = deque(c for c, d in indeg.items() if d == 0)
        out: list[str] = []
        while q:
            c = q.popleft()
            out.append(c)
            for nb in adj[c]:
                indeg[nb] -= 1
                if indeg[nb] == 0:
                    q.append(nb)
        return ''.join(out) if len(out) == len(indeg) else ""

var alienOrder = function(words) {
    const adj = new Map();
    const indeg = new Map();
    for (const w of words) {
        for (const c of w) {
            if (!indeg.has(c)) indeg.set(c, 0);
            if (!adj.has(c)) adj.set(c, 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 "";
        const lim = Math.min(a.length, b.length);
        for (let j = 0; j < lim; j++) {
            if (a[j] !== b[j]) {
                if (!adj.get(a[j]).has(b[j])) {
                    adj.get(a[j]).add(b[j]);
                    indeg.set(b[j], indeg.get(b[j]) + 1);
                }
                break;
            }
        }
    }
    const q = [];
    for (const [c, d] of indeg) if (d === 0) q.push(c);
    const out = [];
    let head = 0;
    while (head < q.length) {
        const c = q[head++];
        out.push(c);
        for (const nb of adj.get(c)) {
            indeg.set(nb, indeg.get(nb) - 1);
            if (indeg.get(nb) === 0) q.push(nb);
        }
    }
    return out.length === indeg.size ? out.join('') : "";
};

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indeg = new HashMap<>();
        for (String w : words) {
            for (char c : w.toCharArray()) {
                indeg.putIfAbsent(c, 0);
                adj.putIfAbsent(c, new HashSet<>());
            }
        }
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            if (a.length() > b.length() && a.startsWith(b)) return "";
            int lim = Math.min(a.length(), b.length());
            for (int j = 0; j < lim; j++) {
                char ca = a.charAt(j), cb = b.charAt(j);
                if (ca != cb) {
                    if (adj.get(ca).add(cb)) {
                        indeg.put(cb, indeg.get(cb) + 1);
                    }
                    break;
                }
            }
        }
        Deque<Character> q = new ArrayDeque<>();
        for (Map.Entry<Character, Integer> e : indeg.entrySet()) {
            if (e.getValue() == 0) q.offer(e.getKey());
        }
        StringBuilder out = new StringBuilder();
        while (!q.isEmpty()) {
            char c = q.poll();
            out.append(c);
            for (char nb : adj.get(c)) {
                indeg.put(nb, indeg.get(nb) - 1);
                if (indeg.get(nb) == 0) q.offer(nb);
            }
        }
        return out.length() == indeg.size() ? out.toString() : "";
    }
}

function alienOrder(words: string[]): string {
    const adj = new Map<string, Set<string>>();
    const indeg = new Map<string, number>();
    for (const w of words) {
        for (const c of w) {
            if (!indeg.has(c)) indeg.set(c, 0);
            if (!adj.has(c)) adj.set(c, 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 "";
        const lim = Math.min(a.length, b.length);
        for (let j = 0; j < lim; j++) {
            if (a[j] !== b[j]) {
                if (!adj.get(a[j])!.has(b[j])) {
                    adj.get(a[j])!.add(b[j]);
                    indeg.set(b[j], indeg.get(b[j])! + 1);
                }
                break;
            }
        }
    }
    const q: string[] = [];
    for (const [c, d] of indeg) if (d === 0) q.push(c);
    const out: string[] = [];
    let head = 0;
    while (head < q.length) {
        const c = q[head++];
        out.push(c);
        for (const nb of adj.get(c)!) {
            indeg.set(nb, indeg.get(nb)! - 1);
            if (indeg.get(nb) === 0) q.push(nb);
        }
    }
    return out.length === indeg.size ? out.join('') : "";
}