G-26. Alien Dictionary - Topological Sort

This comprehensive study note explores the Alien Dictionary problem, translating sequential ordering clues from an unfamiliar language's lexicon into a directed graph and resolving the exact character sequence using Topological Sort.

1. Why Do We Need This? (Problem Statement & Status Quo)

In standard computer science problems, we often deal with predefined sorting orders like the English alphabetical sequence (a through z). However, real-world systems—such as deciphering ancient scripts, parsing custom configuration files, or understanding unknown alien languages—require us to deduce the underlying lexicographical ordering directly from a given sequence of sorted words.

• The Challenge: Given $N$ words from an alien dictionary containing the first $K$ standard alphabets, determine the correct relative order of characters.
• The Ambiguity: Multiple valid orders may exist for a given test case; returning any single correct sequence is sufficient.
• The Underlying Principle: If word $A$ appears before word $B$ in a dictionary, their first differing character establishes a strict precedence rule: character_in_A must come before character_in_B.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Phonebook and Encyclopedia Sorting

Imagine looking up names in a foreign phonebook where you don't know the alphabet. If you see "BBA" listed before "ABCD", you instantly deduce that according to this specific dictionary's rules, the letter 'B' must precede 'A'.

By comparing adjacent word pairs across the entire dictionary, we collect a series of pairwise precedence constraints (e.g., "X must come before Y"). This naturally translates into building a Directed Acyclic Graph (DAG) where nodes are characters and directed edges represent precedence constraints.

3. Step-by-Step Evolution of the Approach

Step 1: Normalizing Alphabets to Integers

To build our graph efficiently, we map characters to zero-based integer indices:

• 'a' $\rightarrow$ 0
• 'b' $\rightarrow$ 1
• 'c' $\rightarrow$ 2
• $\dots$
• Character $C$ $\rightarrow$ C - 'a'

Step 2: Extracting Precedence Edges from Adjacent Pairs

We iterate through the dictionary from index 0 to n - 2, comparing adjacent words:

• S1 = dictionary[i]
• S2 = dictionary[i + 1]

We scan both strings character by character using a pointer until we find the first mismatch. The character from S1 must appear before the character from S2.

4. Complete Flow Walkthrough: Graph Construction

Let's trace how the directed graph (DG) is constructed using code logic.

vector<int> adj[K];
for (int i = 0; i < n - 1; i++) {
    string s1 = dict[i];
    string s2 = dict[i + 1];
    int len = min(s1.size(), s2.size());
    
    for (int ptr = 0; ptr < len; ptr++) {
        if (s1[ptr] != s2[ptr]) {
            adj[s1[ptr] - 'a'].push_back(s2[ptr] - 'a');
            break; // Stop after finding the first differentiating factor
        }
    }
}

Handling Isolated Components

If the alphabet size $K$ is larger than the number of characters actively appearing in the dictionary pairs, those extra characters act as isolated single nodes in our directed graph. Topological sort algorithms (like Kahn's Algorithm or DFS-based post-order reversal) seamlessly handle these disconnected components.

5. Applying Topological Sort

Once our adjacency list represents all pairwise dependencies, the problem simplifies directly to Topological Sorting of a Directed Acyclic Graph (DAG).

Topological Sort Implementation Sketch

// Assuming a standard topoSort helper function exists:
vector<int> topo = topoSort(K, adj);

string alienOrder = "";
for (int node : topo) {
    alienOrder += (char)(node + 'a');
}
return alienOrder;

6. Real-World Practical Pitfalls & Edge Cases

When interviewing or building production-grade parsers, interviewers often ask: When is a dictionary invalid / when is an alien order impossible?

Case 1: Prefix Rule Violation (Invalid Length Ordering)

If a longer string appears before its exact prefix (e.g., "abcd" appears before "abc"), no valid order exists because a prefix must always precede its extension in any valid lexicographical scheme.

Case 2: Cyclic Dependency

If the rules imply a circular relationship (e.g., a appears before b, b appears before c, and c appears before a), a cycle is formed.

Note: Topological sort is mathematically impossible on graphs containing cycles. If a cycle is detected during dependency resolution, the alien dictionary is malformed and contradictory.

7. Summary and Key Takeaways

• Problem Reduction: The alien dictionary problem reduces directly to finding a topological sort on a directed graph.
• Pairwise Comparison: Edges are formed by comparing adjacent words and identifying the first differentiating character.
• Index Normalization: Subtracting 'a' maps letters (a-z) cleanly to integer indices (0-25).
• Short-Circuiting: Always break the character comparison loop immediately after finding the first mismatch between two adjacent words.
• Handling Extra Alphabets: Total vertices $K$ dictates graph size, ensuring isolated alphabets not present in word pairs are still included in the final output.
• Invalid Dictionary Detection: Watch out for invalid prefix orderings (longer string before prefix) and cyclic dependencies where topological sorting fails.