Alien Dictionary

HardGraphs

Given words sorted lexicographically in an alien language, derive a valid ordering of its letters, or return empty if none exists.

Open problem

Constraints

1 <= words.length <= 100
Lowercase letters

Topological sort of letter order

Time O(total characters)Space O(1) (fixed alphabet)

Compare adjacent words to find the first differing letter, which gives an order edge. Topologically sort the letters; a cycle (or a prefix conflict) means no valid ordering.

#include <bits/stdc++.h>
using namespace std;

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