Alien Dictionary

How it works

From the sorted alien words, each pair of adjacent words gives you a letter-order rule at the first mismatching character:

• if w1[j] != w2[j], then w1[j] -> w2[j] (meaning w1[j] comes before w2[j]).

These rules form a directed graph. The alien alphabet is just a topological ordering of this graph.

Kahn's algorithm (BFS topological sort) works by:

• Counting how many prerequisites each letter has (indegree).
• Always picking letters with indegree = 0 (no unmet prerequisites) and "removing" them from the graph.

If there's a cycle, some letters will never reach indegree 0, so we won't be able to output all letters.

Also invalid input case:

• If a longer word comes before its own prefix (e.g., "abc" before "ab"), ordering is impossible.

Steps

1. Create a graph node for every unique character in all words.
2. For each adjacent pair (w1, w2):
   • If w1 starts with w2 and len(w1) > len(w2), return "".
   • Find the first index j where they differ and add edge w1[j] -> w2[j] (only once).
   • Increase indegree[w2[j]] when you add a new edge.
3. Push all characters with indegree = 0 into a queue.
4. While the queue is not empty:
   • Pop a character, add it to the answer.
   • For each neighbor, decrement its indegree.
   • If a neighbor becomes 0, push it into the queue.
5. If the answer contains fewer characters than total unique characters, a cycle exists - return "".
6. Otherwise, join the answer list and return it.

Complexity

• Time complexity: O(N + V + E)
• Space complexity: O(V + E)

Where V is the number of unique characters, E is the number of edges and N is the sum of lengths of all the strings.

Things to watch for

Missing the Invalid Prefix Case

When a longer word appears before its own prefix (e.g., "abc" before "ab"), this is an invalid ordering that cannot exist in any alphabet. Failing to detect this case and return an empty string leads to incorrect results or undefined behavior.

Only Comparing Adjacent Words Partially

The ordering information comes from the first differing character between adjacent words. A common mistake is comparing all differing characters or only comparing the first characters. You must find the first position where characters differ and extract exactly one edge from that comparison.

Not Including All Characters in the Result

Characters that appear in the words but have no ordering constraints (no incoming or outgoing edges) must still appear in the final alphabet. Forgetting to initialize nodes for all unique characters causes some letters to be missing from the output.

Incorrect Cycle Detection in DFS

The three-state visited tracking (unvisited, visiting, visited) is crucial for detecting cycles. Using only two states (visited/unvisited) cannot distinguish between a back edge (cycle) and a cross edge (already processed node). This leads to either false cycle detection or missing actual cycles.

Adding Duplicate Edges

When the same character pair appears from multiple adjacent word comparisons, adding duplicate edges inflates the indegree count in Kahn's algorithm, preventing nodes from ever reaching zero indegree. Use a set to track existing edges before adding new ones.

from collections import deque

class Solution:
    def alienOrder(self, words):
        adj = {c: set() for w in words for c in w}
        indegree = {c: 0 for c in adj}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            minLen = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
                return ""
            for j in range(minLen):
                if w1[j] != w2[j]:
                    if w2[j] not in adj[w1[j]]:
                        adj[w1[j]].add(w2[j])
                        indegree[w2[j]] += 1
                    break

        q = deque([c for c in indegree if indegree[c] == 0])
        res = []

        while q:
            char = q.popleft()
            res.append(char)
            for neighbor in adj[char]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    q.append(neighbor)

        if len(res) != len(indegree):
            return ""

        return "".join(res)

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> adj;
        unordered_map<char, int> indegree;
        for (string w : words) {
            for (char c : w) {
                adj[c] = unordered_set<char>();
                indegree[c] = 0;
            }
        }

        for (int i = 0; i < words.size() - 1; i++) {
            string w1 = words[i], w2 = words[i + 1];
            int minLen = min(w1.size(), w2.size());
            if (w1.size() > w2.size() &&
                w1.substr(0, minLen) == w2.substr(0, minLen)) {
                return "";
            }
            for (int j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    if (!adj[w1[j]].count(w2[j])) {
                        adj[w1[j]].insert(w2[j]);
                        indegree[w2[j]]++;
                    }
                    break;
                }
            }
        }

        queue<char> q;
        for (auto &[c, deg] : indegree) {
            if (deg == 0) {
                q.push(c);
            }
        }

        string res;
        while (!q.empty()) {
            char char_ = q.front();
            q.pop();
            res += char_;
            for (char neighbor : adj[char_]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return res.size() == indegree.size() ? res : "";
    }
};