Definition
- Alien Dictionary – derives a valid character ordering from a list of words sorted in an unknown alphabet's order.
- Edge extraction – for each adjacent pair of words, the first differing character gives a directed edge: the character from the earlier word precedes the character from the later word.
- Topological sort – Kahn's algorithm processes characters with zero in-degree, producing a valid linear ordering.
- Cycle detection – if the final ordering has fewer characters than the graph, a cycle means the input is contradictory.
- Prefix check – if a later word is a strict prefix of an earlier word, the input is invalid.
The National Bank of India receives a list of product tier codes already sorted by an internal ranking whose rule is unknown. Rajesh wants to recover the ranking of the individual tier symbols by examining which symbol comes before which in adjacent code pairs.
Understanding the Concepts
What is the Alien Dictionary problem?
Given a list of words sorted according to the rules of an unknown alphabet, determine a valid ordering of the characters in that alphabet. For example, given the sorted words ["WRT", "WRF", "ER", "ETT", "RFTT"], the derived alphabet order is W, E, R, T, F (or similar valid orderings).
package com.bank.core;
// Sorted words: ["WRT", "WRF", "ER", "ETT", "RFTT"]
// Compare adjacent pairs:
// "WRT" vs "WRF": first diff at index 2 -> T before F
// "WRF" vs "ER": first diff at index 0 -> W before E
// "ER" vs "ETT": first diff at index 1 -> R before T
// "ETT" vs "RFTT": first diff at index 0 -> E before R
// Edges: T->F, W->E, R->T, E->R
// Topological order: W, E, R, T, F
How do you extract ordering edges?
For each adjacent pair of words, compare them character by character until the first position where they differ. The character in the earlier word comes before the character in the later word. Only this first difference gives information; subsequent differences tell you nothing because the ordering was already determined by the first.
package com.bank.core;
// words[i] = "WRT", words[i+1] = "WRF"
// index 0: W == W -> no info
// index 1: R == R -> no info
// index 2: T != F -> edge: T comes before F
// Stop here. Characters after the first difference give no ordering info.
How do you build the graph and run topological sort?
First collect all distinct characters as nodes. Then extract edges from adjacent word pairs. Build an adjacency list and an in-degree map. Run Kahn's algorithm: enqueue all zero in-degree characters, poll them one by one, decrement the in-degree of their neighbors, and enqueue neighbors that reach zero.
package com.bank.service;
import java.util.*;
public class AlienDictionary {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> adj = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();
// Initialize all characters
for (String word : words) {
for (char c : word.toCharArray()) {
adj.putIfAbsent(c, new HashSet<>());
inDegree.putIfAbsent(c, 0);
}
}
// Extract edges from adjacent pairs
for (int i = 0; i < words.length - 1; i++) {
String w1 = words[i];
String w2 = words[i + 1];
int minLen = Math.min(w1.length(), w2.length());
// Prefix check: invalid if w1 is longer and starts with w2
if (w1.length() > w2.length()
&& w1.startsWith(w2)) {
return ""; // invalid input
}
for (int j = 0; j < minLen; j++) {
char c1 = w1.charAt(j);
char c2 = w2.charAt(j);
if (c1 != c2) {
if (!adj.get(c1).contains(c2)) {
adj.get(c1).add(c2);
inDegree.merge(c2, 1, Integer::sum);
}
break; // only first difference matters
}
}
}
// Kahn's algorithm
Queue<Character> queue = new LinkedList<>();
for (Map.Entry<Character, Integer> entry : inDegree.entrySet()) {
if (entry.getValue() == 0) {
queue.offer(entry.getKey());
}
}
StringBuilder order = new StringBuilder();
while (!queue.isEmpty()) {
char c = queue.poll();
order.append(c);
for (char neighbor : adj.get(c)) {
inDegree.merge(neighbor, -1, Integer::sum);
if (inDegree.get(neighbor) == 0) {
queue.offer(neighbor);
}
}
}
// Cycle check
if (order.length() != inDegree.size()) {
return ""; // cycle detected, contradictory input
}
return order.toString();
}
public static void main(String[] args) {
AlienDictionary solver = new AlienDictionary();
System.out.println(solver.alienOrder(
new String[]{"WRT", "WRF", "ER", "ETT", "RFTT"}));
}
}
WERTF
Why does only the first differing character give information?
In a sorted list, adjacent words are ordered by the first position where they differ, just like in a standard dictionary. Characters after the first difference are in the context of that first character's ordering, not the overall alphabet ordering. Using subsequent differences would introduce incorrect edges.
package com.bank.core;
// "ER" vs "ETT"
// index 0: E == E -> no info
// index 1: R != T -> R comes before T
// Do NOT compare further: the second 'T' in "ETT" tells us nothing
// about T's position relative to other characters
What is the prefix edge case?
If a later word is a strict prefix of an earlier word (for example, ["ABC", "AB"]), the input is invalid. In any correctly sorted dictionary, a shorter word that is a prefix always comes before the longer word. If the opposite appears, the dictionary is contradictory.
package com.bank.core;
// INVALID: ["ABC", "AB"]
// "AB" is a prefix of "ABC" but appears after it
// A valid sort would have "AB" before "ABC"
// Return empty string to indicate invalid input
What are the edge cases?
Edge cases include: single word (all characters have no ordering constraints), two identical words (no edges extracted), contradictory ordering (cycle in graph), and characters that appear in words but have no ordering constraints relative to each other.
package com.bank.core;
// Edge case 1: single word ["ABC"] -> "ABC" or any order (no constraints)
// Edge case 2: ["AA", "AA"] -> no edges, all chars unconstrained
// Edge case 3: cycle -> return ""
// Edge case 4: multiple valid orderings (topological sort is not unique)
What about a banking use case?
At the National Bank of India, product tier codes are sorted by an internal ranking whose rule over individual symbols is unknown. Rajesh extracts the ranking from adjacent code comparisons.
package com.bank.service;
public class TierRankingRecovery {
private final AlienDictionary solver = new AlienDictionary();
public String recoverRanking(String[] sortedCodes) {
String ranking = solver.alienOrder(sortedCodes);
if (ranking.isEmpty()) {
System.out.println("ERROR: Contradictory tier ordering");
} else {
System.out.println("Recovered tier ranking: " + ranking);
}
return ranking;
}
public static void main(String[] args) {
TierRankingRecovery recovery = new TierRankingRecovery();
recovery.recoverRanking(new String[]{"PA", "PB", "GA", "GB"});
}
}
Recovered tier ranking: PABG
What are common mistakes?
The most common mistake is forgetting the prefix check, which lets invalid inputs slip through. Another mistake is extracting edges from all differing positions instead of only the first. A third mistake is not initializing all characters as nodes, which can cause characters with no edges to be missing from the output.
package com.bank.core;
// WRONG: extracting edges from ALL differing positions
for (int j = 0; j < minLen; j++) {
if (w1.charAt(j) != w2.charAt(j)) {
addEdge(w1.charAt(j), w2.charAt(j)); // WRONG: must break after first
}
}
// CORRECT: break after first difference
for (int j = 0; j < minLen; j++) {
if (w1.charAt(j) != w2.charAt(j)) {
addEdge(w1.charAt(j), w2.charAt(j));
break; // only first difference gives info
}
}
What should a senior engineer know?
A senior engineer should know that the time complexity is O(C) where C is the total number of characters across all words, because each character is visited once during graph construction and once during topological sort. The space is bounded by the alphabet size. Multiple valid topological orderings may exist when the graph has ambiguity; the problem asks for any valid one. DFS-based topological sort is an alternative to Kahn's algorithm but requires careful cycle detection with coloring.
package com.bank.core;
// Senior notes:
// 1. Time: O(C) total characters, not O(n * maxWordLen)
// 2. Space: O(1) bounded by alphabet size (at most 26 chars)
// 3. Multiple valid orderings possible (graph may have ambiguity)
// 4. DFS alternative: post-order reversal with 3-color cycle detection
// 5. Kahn's is preferred for clarity and natural cycle detection
Visual Overview
Alien Dictionary: words = ["WRT", "WRF", "ER", "ETT", "RFTT"] Step 1: Extract edges from adjacent pairs ┌──────────────────────────────────────────┐ │ "WRT" vs "WRF" -> T before F (T -> F) │ │ "WRF" vs "ER" -> W before E (W -> E) │ │ "ER" vs "ETT" -> R before T (R -> T) │ │ "ETT" vs "RFTT"-> E before R (E -> R) │ └──────────────────────────────────────────┘ Step 2: Build graph ┌──────────────────────────────────────────┐ │ W ──→ E ──→ R ──→ T ──→ F │ │ │ │ In-degrees: W:0, E:1, R:1, T:1, F:1 │ └──────────────────────────────────────────┘ Step 3: Kahn's algorithm (BFS topological sort) ┌──────────────────────────────────────────┐ │ Queue: [W] (only zero in-degree) │ │ Poll W -> order="W", reduce E to 0 │ │ Queue: [E] │ │ Poll E -> order="WE", reduce R to 0 │ │ Queue: [R] │ │ Poll R -> order="WER", reduce T to 0 │ │ Queue: [T] │ │ Poll T -> order="WERT", reduce F to 0 │ │ Queue: [F] │ │ Poll F -> order="WERTF" │ │ │ │ Length 5 == 5 chars -> no cycle │ └──────────────────────────────────────────┘ Result: "WERTF"
Key Takeaway
The Alien Dictionary problem derives a valid character ordering from a list of words sorted according to an unknown alphabet. The approach is a graph-construction application of the Topological Sort pattern. You compare each adjacent pair of words to find the first position where they differ, which gives a directed edge: the character from the earlier word precedes the character from the later word. Only this first difference is informative; subsequent differences are meaningless.
After extracting all edges, you build a directed graph of characters and run Kahn's algorithm. Characters with zero in-degree are enqueued first and emitted in order. When a character is processed, its neighbors' in-degrees are decremented, and any that reach zero are enqueued. If the final order has fewer characters than the total, a cycle exists and the input is contradictory.
Two critical checks prevent invalid inputs from slipping through. First, if a later word is a strict prefix of an earlier word, the dictionary is invalid because shorter prefixes always come first in any valid sort. Second, characters that appear in words but have no ordering edges must still be initialized as nodes so they appear in the output. Missing either check is a common source of bugs.
At the National Bank of India, Rajesh used this to recover the rank order of product tier symbols from a list of tier codes that were already sorted by an internal ranking rule. He extracted ordering edges from adjacent code comparisons and topologically sorted the symbols. The result was the internal ranking that had been implicit in the sorted list.
Remember one sentence: compare adjacent word pairs for the first differing character to build a directed graph of character precedence, then topologically sort the characters.
---