Alien Dictionary

Given a sorted dictionary of alien language, find the order of characters in the alien alphabet

Language Selection

Choose your preferred programming language

Showing: Python

Alien Dictionary

Problem Statement

There is a new alien language that uses the Latin alphabet. However, the order among the letters is unknown to you. You are given a list of strings words from the alien language’s dictionary, where the strings in words are sorted lexicographically by the rules of this alien language.

Return a string of the unique letters in the new alien alphabet in lexicographically smallest order. If there is no solution, return an empty string. If there are multiple valid orders, return any one of them.

Input/Output Specifications

Input: A list of strings words representing words from an alien dictionary in sorted order
Output: A string representing the order of characters in the alien alphabet, or empty string if no valid order exists

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters
words are sorted lexicographically according to the alien language

Examples

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Explanation: 
From "wrt" and "wrf" → t comes before f
From "wrf" and "er" → w comes before e  
From "er" and "ett" → r comes before t
From "ett" and "rftt" → e comes before r
Order: w → e → r → t → f

Example 2:

Input: words = ["z","x"]
Output: "zx"
Explanation: From "z" and "x" → z comes before x

Example 3:

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is inconsistent, no valid alien alphabet exists

Example 4:

Input: words = ["abc","ab"]
Output: ""
Explanation: "abc" should not come before "ab" if sorted, invalid input

Solution Approaches

Approach 1: Topological Sort using DFS (Optimal)

Algorithm Explanation:

Build a directed graph representing character ordering relationships
For adjacent words, find the first differing character to establish precedence
Perform topological sort using DFS to find valid ordering
Detect cycles to identify invalid input

Implementation:

Python:

def alien_order(words):
    """
    Find alien alphabet order using topological sort with DFS
    Time: O(C) where C is total length of all words
    Space: O(1) since at most 26 characters
    """
    # Step 1: Create graph and in-degree count
    graph = {}
    in_degree = {}
    
    # Initialize all characters
    for word in words:
        for char in word:
            if char not in graph:
                graph[char] = set()
                in_degree[char] = 0
    
    # Step 2: Build graph by comparing adjacent words
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))
        
        # Check for invalid case: longer word is prefix of shorter
        if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
            return ""
        
        # Find first different character
        for j in range(min_len):
            if word1[j] != word2[j]:
                # word1[j] comes before word2[j]
                if word2[j] not in graph[word1[j]]:
                    graph[word1[j]].add(word2[j])
                    in_degree[word2[j]] += 1
                break
    
    # Step 3: Topological sort using DFS
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {char: WHITE for char in graph}
    result = []
    
    def dfs(node):
        if color[node] == GRAY:  # Cycle detected
            return False
        if color[node] == BLACK:  # Already processed
            return True
        
        color[node] = GRAY
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        
        color[node] = BLACK
        result.append(node)  # Post-order
        return True
    
    # Visit all nodes
    for char in graph:
        if color[char] == WHITE:
            if not dfs(char):
                return ""  # Cycle detected
    
    return ''.join(reversed(result))

def alien_order_kahn(words):
    """
    Alternative using Kahn's algorithm (BFS-based topological sort)
    Time: O(C)
    Space: O(1)
    """
    from collections import deque
    
    graph = {}
    in_degree = {}
    
    # Initialize
    for word in words:
        for char in word:
            if char not in graph:
                graph[char] = []
                in_degree[char] = 0
    
    # Build graph
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))
        
        if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
            return ""
        
        for j in range(min_len):
            if word1[j] != word2[j]:
                if word2[j] not in graph[word1[j]]:
                    graph[word1[j]].append(word2[j])
                    in_degree[word2[j]] += 1
                break
    
    # Kahn's algorithm
    queue = deque([char for char in in_degree if in_degree[char] == 0])
    result = []
    
    while queue:
        char = queue.popleft()
        result.append(char)
        
        for neighbor in graph[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(result) != len(graph):
        return ""  # Cycle exists
    
    return ''.join(result)

Java:

class Solution {
    /**
     * Find alien alphabet order using DFS-based topological sort
     * Time: O(C) where C is total length of all words
     * Space: O(1) since at most 26 characters
     */
    public String alienOrder(String[] words) {
        // Build graph
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        
        // Initialize all characters
        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.putIfAbsent(c, new HashSet<>());
                inDegree.putIfAbsent(c, 0);
            }
        }
        
        // Build edges
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i], word2 = words[i + 1];
            int minLen = Math.min(word1.length(), word2.length());
            
            // Invalid case check
            if (word1.length() > word2.length() && 
                word1.substring(0, minLen).equals(word2.substring(0, minLen))) {
                return "";
            }
            
            for (int j = 0; j < minLen; j++) {
                char c1 = word1.charAt(j), c2 = word2.charAt(j);
                if (c1 != c2) {
                    if (!graph.get(c1).contains(c2)) {
                        graph.get(c1).add(c2);
                        inDegree.put(c2, inDegree.get(c2) + 1);
                    }
                    break;
                }
            }
        }
        
        // DFS-based topological sort
        Map<Character, Integer> state = new HashMap<>();
        // 0: white, 1: gray, 2: black
        StringBuilder result = new StringBuilder();
        
        for (char c : graph.keySet()) {
            if (state.getOrDefault(c, 0) == 0) {
                if (!dfs(c, graph, state, result)) {
                    return "";
                }
            }
        }
        
        return result.reverse().toString();
    }
    
    private boolean dfs(char node, Map<Character, Set<Character>> graph,
                       Map<Character, Integer> state, StringBuilder result) {
        if (state.getOrDefault(node, 0) == 1) return false; // Cycle
        if (state.getOrDefault(node, 0) == 2) return true;  // Visited
        
        state.put(node, 1); // Gray
        
        for (char neighbor : graph.get(node)) {
            if (!dfs(neighbor, graph, state, result)) {
                return false;
            }
        }
        
        state.put(node, 2); // Black
        result.append(node);
        return true;
    }
    
    /**
     * Alternative using Kahn's algorithm
     */
    public String alienOrderKahn(String[] words) {
        Map<Character, List<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        
        // Initialize
        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.putIfAbsent(c, new ArrayList<>());
                inDegree.putIfAbsent(c, 0);
            }
        }
        
        // Build graph
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i], word2 = words[i + 1];
            int minLen = Math.min(word1.length(), word2.length());
            
            if (word1.length() > word2.length() && 
                word1.substring(0, minLen).equals(word2)) {
                return "";
            }
            
            for (int j = 0; j < minLen; j++) {
                char c1 = word1.charAt(j), c2 = word2.charAt(j);
                if (c1 != c2) {
                    graph.get(c1).add(c2);
                    inDegree.put(c2, inDegree.get(c2) + 1);
                    break;
                }
            }
        }
        
        // Kahn's algorithm
        Queue<Character> queue = new LinkedList<>();
        for (char c : inDegree.keySet()) {
            if (inDegree.get(c) == 0) {
                queue.offer(c);
            }
        }
        
        StringBuilder result = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            result.append(c);
            
            for (char neighbor : graph.get(c)) {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return result.length() == graph.size() ? result.toString() : "";
    }
}

Go:

// alienOrder - Find alien alphabet order using DFS topological sort
// Time: O(C) where C is total length of all words
// Space: O(1) since at most 26 characters
func alienOrder(words []string) string {
    // Build graph
    graph := make(map[rune]map[rune]bool)
    inDegree := make(map[rune]int)
    
    // Initialize all characters
    for _, word := range words {
        for _, char := range word {
            if _, exists := graph[char]; !exists {
                graph[char] = make(map[rune]bool)
                inDegree[char] = 0
            }
        }
    }
    
    // Build edges
    for i := 0; i < len(words)-1; i++ {
        word1, word2 := []rune(words[i]), []rune(words[i+1])
        minLen := len(word1)
        if len(word2) < minLen {
            minLen = len(word2)
        }
        
        // Check for invalid case
        if len(word1) > len(word2) && string(word1[:minLen]) == string(word2[:minLen]) {
            return ""
        }
        
        for j := 0; j < minLen; j++ {
            if word1[j] != word2[j] {
                if !graph[word1[j]][word2[j]] {
                    graph[word1[j]][word2[j]] = true
                    inDegree[word2[j]]++
                }
                break
            }
        }
    }
    
    // DFS-based topological sort
    const (
        WHITE = 0
        GRAY  = 1
        BLACK = 2
    )
    
    state := make(map[rune]int)
    var result []rune
    
    var dfs func(rune) bool
    dfs = func(node rune) bool {
        if state[node] == GRAY {
            return false // Cycle detected
        }
        if state[node] == BLACK {
            return true // Already processed
        }
        
        state[node] = GRAY
        for neighbor := range graph[node] {
            if !dfs(neighbor) {
                return false
            }
        }
        
        state[node] = BLACK
        result = append(result, node)
        return true
    }
    
    // Visit all nodes
    for char := range graph {
        if state[char] == WHITE {
            if !dfs(char) {
                return ""
            }
        }
    }
    
    // Reverse result (post-order)
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }
    
    return string(result)
}

// alienOrderKahn - Alternative using Kahn's algorithm
func alienOrderKahn(words []string) string {
    graph := make(map[rune][]rune)
    inDegree := make(map[rune]int)
    
    // Initialize
    for _, word := range words {
        for _, char := range word {
            if _, exists := graph[char]; !exists {
                graph[char] = []rune{}
                inDegree[char] = 0
            }
        }
    }
    
    // Build graph
    for i := 0; i < len(words)-1; i++ {
        word1, word2 := []rune(words[i]), []rune(words[i+1])
        minLen := len(word1)
        if len(word2) < minLen {
            minLen = len(word2)
        }
        
        if len(word1) > len(word2) && string(word1[:minLen]) == string(word2[:minLen]) {
            return ""
        }
        
        for j := 0; j < minLen; j++ {
            if word1[j] != word2[j] {
                graph[word1[j]] = append(graph[word1[j]], word2[j])
                inDegree[word2[j]]++
                break
            }
        }
    }
    
    // Kahn's algorithm
    var queue []rune
    for char := range inDegree {
        if inDegree[char] == 0 {
            queue = append(queue, char)
        }
    }
    
    var result []rune
    for len(queue) > 0 {
        char := queue[0]
        queue = queue[1:]
        result = append(result, char)
        
        for _, neighbor := range graph[char] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
    
    if len(result) != len(graph) {
        return ""
    }
    
    return string(result)
}

JavaScript:

/**
 * Find alien alphabet order using DFS-based topological sort
 * Time: O(C) where C is total length of all words
 * Space: O(1) since at most 26 characters
 */
function alienOrder(words) {
    // Build graph
    const graph = new Map();
    const inDegree = new Map();
    
    // Initialize all characters
    for (const word of words) {
        for (const char of word) {
            if (!graph.has(char)) {
                graph.set(char, new Set());
                inDegree.set(char, 0);
            }
        }
    }
    
    // Build edges
    for (let i = 0; i < words.length - 1; i++) {
        const word1 = words[i], word2 = words[i + 1];
        const minLen = Math.min(word1.length, word2.length);
        
        // Check for invalid case
        if (word1.length > word2.length && 
            word1.substring(0, minLen) === word2.substring(0, minLen)) {
            return "";
        }
        
        for (let j = 0; j < minLen; j++) {
            if (word1[j] !== word2[j]) {
                if (!graph.get(word1[j]).has(word2[j])) {
                    graph.get(word1[j]).add(word2[j]);
                    inDegree.set(word2[j], inDegree.get(word2[j]) + 1);
                }
                break;
            }
        }
    }
    
    // DFS-based topological sort
    const WHITE = 0, GRAY = 1, BLACK = 2;
    const state = new Map();
    const result = [];
    
    function dfs(node) {
        if (state.get(node) === GRAY) return false; // Cycle
        if (state.get(node) === BLACK) return true; // Processed
        
        state.set(node, GRAY);
        for (const neighbor of graph.get(node)) {
            if (!dfs(neighbor)) return false;
        }
        
        state.set(node, BLACK);
        result.push(node);
        return true;
    }
    
    // Visit all nodes
    for (const char of graph.keys()) {
        if (!state.has(char) || state.get(char) === WHITE) {
            if (!dfs(char)) return "";
        }
    }
    
    return result.reverse().join('');
}

/**
 * Alternative using Kahn's algorithm (BFS)
 */
function alienOrderKahn(words) {
    const graph = new Map();
    const inDegree = new Map();
    
    // Initialize
    for (const word of words) {
        for (const char of word) {
            if (!graph.has(char)) {
                graph.set(char, []);
                inDegree.set(char, 0);
            }
        }
    }
    
    // Build graph
    for (let i = 0; i < words.length - 1; i++) {
        const word1 = words[i], word2 = words[i + 1];
        const minLen = Math.min(word1.length, word2.length);
        
        if (word1.length > word2.length && 
            word1.substring(0, minLen) === word2) {
            return "";
        }
        
        for (let j = 0; j < minLen; j++) {
            if (word1[j] !== word2[j]) {
                graph.get(word1[j]).push(word2[j]);
                inDegree.set(word2[j], inDegree.get(word2[j]) + 1);
                break;
            }
        }
    }
    
    // Kahn's algorithm
    const queue = [];
    for (const [char, degree] of inDegree) {
        if (degree === 0) queue.push(char);
    }
    
    const result = [];
    while (queue.length > 0) {
        const char = queue.shift();
        result.push(char);
        
        for (const neighbor of graph.get(char)) {
            inDegree.set(neighbor, inDegree.get(neighbor) - 1);
            if (inDegree.get(neighbor) === 0) {
                queue.push(neighbor);
            }
        }
    }
    
    return result.length === graph.size ? result.join('') : "";
}

// ES6 version with modern syntax
const alienOrderES6 = (words) => {
    const graph = new Map();
    const inDegree = new Map();
    
    // Initialize
    words.forEach(word => {
        [...word].forEach(char => {
            if (!graph.has(char)) {
                graph.set(char, new Set());
                inDegree.set(char, 0);
            }
        });
    });
    
    // Build edges
    for (let i = 0; i < words.length - 1; i++) {
        const [word1, word2] = [words[i], words[i + 1]];
        const minLen = Math.min(word1.length, word2.length);
        
        if (word1.length > word2.length && 
            word1.startsWith(word2)) return "";
        
        for (let j = 0; j < minLen; j++) {
            if (word1[j] !== word2[j]) {
                if (!graph.get(word1[j]).has(word2[j])) {
                    graph.get(word1[j]).add(word2[j]);
                    inDegree.set(word2[j], inDegree.get(word2[j]) + 1);
                }
                break;
            }
        }
    }
    
    // DFS topological sort
    const [WHITE, GRAY, BLACK] = [0, 1, 2];
    const state = new Map();
    const result = [];
    
    const dfs = (node) => {
        if (state.get(node) === GRAY) return false;
        if (state.get(node) === BLACK) return true;
        
        state.set(node, GRAY);
        
        for (const neighbor of graph.get(node)) {
            if (!dfs(neighbor)) return false;
        }
        
        state.set(node, BLACK);
        result.push(node);
        return true;
    };
    
    for (const char of graph.keys()) {
        if (!state.has(char) && !dfs(char)) return "";
    }
    
    return result.reverse().join('');
};

C#:

public class Solution {
    /// <summary>
    /// Find alien alphabet order using DFS-based topological sort
    /// Time: O(C) where C is total length of all words
    /// Space: O(1) since at most 26 characters
    /// </summary>
    public string AlienOrder(string[] words) {
        // Build graph
        var graph = new Dictionary<char, HashSet<char>>();
        var inDegree = new Dictionary<char, int>();
        
        // Initialize all characters
        foreach (string word in words) {
            foreach (char c in word) {
                if (!graph.ContainsKey(c)) {
                    graph[c] = new HashSet<char>();
                    inDegree[c] = 0;
                }
            }
        }
        
        // Build edges
        for (int i = 0; i < words.Length - 1; i++) {
            string word1 = words[i], word2 = words[i + 1];
            int minLen = Math.Min(word1.Length, word2.Length);
            
            // Check for invalid case
            if (word1.Length > word2.Length && 
                word1.Substring(0, minLen) == word2.Substring(0, minLen)) {
                return "";
            }
            
            for (int j = 0; j < minLen; j++) {
                if (word1[j] != word2[j]) {
                    if (!graph[word1[j]].Contains(word2[j])) {
                        graph[word1[j]].Add(word2[j]);
                        inDegree[word2[j]]++;
                    }
                    break;
                }
            }
        }
        
        // DFS-based topological sort
        var state = new Dictionary<char, int>(); // 0: white, 1: gray, 2: black
        var result = new List<char>();
        
        bool Dfs(char node) {
            if (state.GetValueOrDefault(node, 0) == 1) return false; // Cycle
            if (state.GetValueOrDefault(node, 0) == 2) return true;  // Processed
            
            state[node] = 1; // Gray
            
            foreach (char neighbor in graph[node]) {
                if (!Dfs(neighbor)) return false;
            }
            
            state[node] = 2; // Black
            result.Add(node);
            return true;
        }
        
        // Visit all nodes
        foreach (char c in graph.Keys) {
            if (state.GetValueOrDefault(c, 0) == 0) {
                if (!Dfs(c)) return "";
            }
        }
        
        result.Reverse();
        return new string(result.ToArray());
    }
    
    /// <summary>
    /// Alternative using Kahn's algorithm with LINQ
    /// </summary>
    public string AlienOrderKahn(string[] words) {
        var graph = new Dictionary<char, List<char>>();
        var inDegree = new Dictionary<char, int>();
        
        // Initialize
        foreach (string word in words) {
            foreach (char c in word) {
                if (!graph.ContainsKey(c)) {
                    graph[c] = new List<char>();
                    inDegree[c] = 0;
                }
            }
        }
        
        // Build graph
        for (int i = 0; i < words.Length - 1; i++) {
            string word1 = words[i], word2 = words[i + 1];
            int minLen = Math.Min(word1.Length, word2.Length);
            
            if (word1.Length > word2.Length && 
                word1.Substring(0, minLen) == word2) {
                return "";
            }
            
            for (int j = 0; j < minLen; j++) {
                if (word1[j] != word2[j]) {
                    graph[word1[j]].Add(word2[j]);
                    inDegree[word2[j]]++;
                    break;
                }
            }
        }
        
        // Kahn's algorithm
        var queue = new Queue<char>(inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key));
        var result = new StringBuilder();
        
        while (queue.Count > 0) {
            char c = queue.Dequeue();
            result.Append(c);
            
            foreach (char neighbor in graph[c]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        return result.Length == graph.Count ? result.ToString() : "";
    }
}

Complexity Analysis:

Time Complexity: O(C) where C is the total length of all words
- Building graph: O(C) to process all characters
- Topological sort: O(V + E) where V ≤ 26 and E ≤ 26²
Space Complexity: O(1) since we have at most 26 characters

Trade-offs:

DFS approach: Easier cycle detection, more intuitive
BFS (Kahn’s): More straightforward implementation, better for some applications
Both have same time complexity for this problem

Key Insights

Lexicographic comparison: Only first differing character matters for ordering
Topological sort: Perfect fit for dependency ordering problems
Cycle detection: Essential for identifying invalid alien dictionaries
Edge cases: Handle prefixes and identical words carefully
Graph sparsity: At most 26 nodes and 26² edges makes this efficient

Edge Cases

Single character words: ["a", "b"] → Simple ordering
Identical words: ["abc", "abc"] → No new information
Prefix conflict: ["abc", "ab"] → Invalid input
Cycles: ["a", "b", "a"] → No valid ordering
Single word: ["abc"] → Return any order of characters
Empty input: [] → Return empty string
Unconnected components: Some characters have no ordering constraints

How Solutions Handle Edge Cases:

Prefix conflict: Explicit check during graph building
Cycles: DFS gray/black coloring or Kahn’s final count check
Single word: All characters treated independently
Unconnected components: Topological sort handles naturally

Test Cases

def test_alien_order():
    # Example 1: Basic case
    words1 = ["wrt","wrf","er","ett","rftt"]
    result1 = alien_order(words1)
    assert result1 == "wertf"
    
    # Example 2: Simple case
    words2 = ["z","x"]
    result2 = alien_order(words2)
    assert result2 == "zx"
    
    # Example 3: Invalid - cycle
    words3 = ["z","x","z"]
    result3 = alien_order(words3)
    assert result3 == ""
    
    # Example 4: Invalid - prefix
    words4 = ["abc","ab"]
    result4 = alien_order(words4)
    assert result4 == ""
    
    # Example 5: Single word
    words5 = ["abc"]
    result5 = alien_order(words5)
    assert len(result5) == 3 and set(result5) == {'a', 'b', 'c'}
    
    # Example 6: Complex valid ordering
    words6 = ["ac","ab","zc","zb"]
    result6 = alien_order(words6)
    # Valid orders: "acbz" or "cazb" etc.
    assert len(result6) == 4 and all(c in result6 for c in "acbz")
    
    # Example 7: Disconnected components
    words7 = ["ab", "cd"]
    result7 = alien_order(words7)
    assert len(result7) == 4
    
    print("All tests passed!")

test_alien_order()

Follow-up Questions

Multiple valid orders: How would you find all possible valid orderings?
Weighted edges: What if some character relationships are stronger than others?
Partial words: How would you handle truncated or partial dictionary?
Real-time updates: How would you handle dynamic dictionary updates?
Lexicographically smallest: How do you ensure the smallest valid order?

Common Mistakes

Not detecting prefix conflicts: Missing invalid case ["abc", "ab"]
- Problem: Invalid input not caught
- Solution: Explicit prefix length check
Incorrect cycle detection: Not properly implementing DFS states
- Problem: Missing cycles or false positives
- Solution: Use three-color DFS (white/gray/black)
Multiple edges: Adding duplicate edges between same characters
- Problem: Incorrect in-degree counts
- Solution: Check for existing edges before adding
Not handling single words: Assuming multiple words always exist
- Problem: Empty result for valid single word
- Solution: Initialize all characters properly

Interview Tips

Clarify input format: Confirm words are given in sorted order
Discuss approach: Explain why topological sort is appropriate
Handle edge cases: Demonstrate awareness of invalid inputs
Choose algorithm: Discuss DFS vs BFS trade-offs
Optimize for constraints: Mention that small alphabet size makes this efficient

Concept Explanations

Topological Sorting: Essential algorithm for ordering items with dependencies. Two main approaches: DFS (using recursion and post-order) and BFS (Kahn’s algorithm using in-degrees).

Dependency Graph: Characters with known ordering relationships form a directed graph where edges represent “comes before” relationships.

When to Apply: Use this pattern for any ordering problem with precedence constraints: course scheduling, build dependencies, task ordering, or any scenario where some items must come before others.