6.5 Alien Dictionary

6.5.1 Problem Metadata

6.5.2 Description

There is a new alien language that uses the English alphabet. However, the order of 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 new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there is no solution, return "". If there are multiple solutions, return any of them.

6.5.3 Examples

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Explanation:
From "wrt" and "wrf", we can get 't' < 'f'
From "wrt" and "er", we can get 'w' < 'e'
From "er" and "ett", we can get 'r' < 't'
From "ett" and "rftt", we can get 'e' < 'r'
So the order is "wertf"

Example 2:

Input: words = ["z","x"]
Output: "zx"
Explanation: From "z" and "x", we can get 'z' < 'x'
So the order is "zx"

Example 3:

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return ""

6.5.4 Constraints

  • \(1 \le\) words.length \(\le\) 100
  • \(1 \le\) words[i].length \(\le\) 100
  • words[i] consists of only lowercase English letters
  • The input is guaranteed to be from a valid alien language dictionary

6.5.5 Solution - Topological Sort with DFS

6.5.5.1 Walkthrough

This problem requires deriving a character ordering from a sorted dictionary. The key insight is modeling this as a directed graph where each character is a node, and an edge A → B means “A comes before B in the alien alphabet.” Once we build this graph, we apply topological sort to find a valid ordering.

Core Algorithm:

  1. Build the dependency graph by comparing adjacent words
  2. Detect invalid inputs (prefix violations and cycles)
  3. Apply DFS-based topological sort to find the ordering

Step 1: Graph Construction

Compare each pair of adjacent words in the input array. The first position where they differ tells us a character ordering constraint.

Example: Given "wrt" and "wrf":

Position 0: 'w' == 'w' → Continue
Position 1: 'r' == 'r' → Continue
Position 2: 't' != 'f' → Found difference!

This tells us t must come before f in the alien alphabet → Add edge t → f.

Critical Edge Cases:

  1. Prefix Violation: If a longer word appears before its prefix (e.g., ["abc", "ab"]), the input is invalid → return "".

  2. Cycle Detection: If the derived graph contains a cycle (e.g., a → b → c → a), no valid ordering exists → return "".

Step 2: Three-State DFS with Cycle Detection

Use DFS-based topological sort with three states to detect cycles:

  • WHITE (0): Node not yet visited
  • GRAY (1): Node currently in the recursion stack (being explored)
  • BLACK (2): Node completely processed (all descendants explored)

Cycle Detection Rule: If we encounter a GRAY node during DFS, we’ve found a back edge (cycle).

Step 3: Build Result from Stack

DFS processes nodes in post-order (children before parents). By pushing nodes onto a stack after processing all their children, popping the stack gives us the topological order.

Visual Example with words = ["wrt", "wrf", "er", "ett", "rftt"]:

Step 1: Build Graph
Compare "wrt" vs "wrf" → t → f
Compare "wrf" vs "er"  → w → e
Compare "er" vs "ett"  → r → t
Compare "ett" vs "rftt" → e → r

Graph: w → e → r → t → f

Step 2: DFS Topological Sort
Start from 'w':
  Visit w (GRAY)
    Visit e (GRAY)
      Visit r (GRAY)
        Visit t (GRAY)
          Visit f (GRAY)
          f complete (BLACK), push to stack: [f]
        t complete (BLACK), push to stack: [f, t]
      r complete (BLACK), push to stack: [f, t, r]
    e complete (BLACK), push to stack: [f, t, r, e]
  w complete (BLACK), push to stack: [f, t, r, e, w]

Step 3: Build Result
Pop stack: "wertf" ✓

Example with Cycle words = ["z", "x", "z"]:

Graph Construction:
Compare "z" vs "x" → z → x
Compare "x" vs "z" → x → z

Graph: z ⟷ x (cycle!)

DFS from 'z':
  state[z] = GRAY
  Visit neighbor 'x':
    state[x] = GRAY
    Visit neighbor 'z':
      state[z] == GRAY → CYCLE DETECTED! ✓
      return false

Result: "" (invalid)

6.5.5.2 Analysis

  • Time Complexity: O(C + E)
    • C is the total number of characters across all words
    • E is the number of edges in the graph (at most 26 edges for lowercase alphabet)
    • Building the graph: O(C) to iterate through all words
    • DFS traversal: O(V + E) where V \(\le\) 26 (constant alphabet size)
    • Overall: O(C) since the graph size is bounded by the constant alphabet
  • Space Complexity: O(1)
    • Graph adjacency list: O(26) for at most 26 characters
    • State array: O(26)
    • Recursion stack: O(26) in worst case
    • All bounded by constant alphabet size, so O(1)

6.5.5.3 Implementation Steps

  1. Initialize graph with all unique characters:
    • Create a HashMap<Character, Set<Character>> for the adjacency list
    • Iterate through all words and add each character as a node (even if it has no edges)
  2. Build edges by comparing adjacent words:
    • For each pair of consecutive words (word1, word2):
      • Check for prefix violation: if word1.length() > word2.length() and word1.startsWith(word2), return ""
      • Find the first position where characters differ
      • Add edge word1[pos] → word2[pos]
      • Break after finding the first difference (only the first difference matters)
  3. Perform DFS with cycle detection:
    • Use an int[] state array with three states: WHITE (0), GRAY (1), BLACK (2)
    • For each unvisited character (WHITE), start DFS
    • In DFS:
      • Mark node as GRAY (currently exploring)
      • For each neighbor:
        • If neighbor is GRAY → cycle detected, return false
        • If neighbor is WHITE → recursively visit it
      • Mark node as BLACK (finished)
      • Push node to stack (post-order)
  4. Build result from stack:
    • Pop all characters from the stack to build the final ordering
    • If cycle was detected, return ""

6.5.5.4 Code - Java

class Solution {
    private static final int WHITE = 0;  // Not visited
    private static final int GRAY = 1;   // Currently exploring (in recursion stack)
    private static final int BLACK = 2;  // Finished exploring

    public String alienOrder(String[] words) {
        // Step 1: Initialize graph with all characters
        Map<Character, Set<Character>> graph = new HashMap<>();

        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.putIfAbsent(c, new HashSet<>());
            }
        }

        // Step 2: Build edges by comparing adjacent words
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            int minLen = Math.min(word1.length(), word2.length());

            // Check for prefix violation
            if (word1.length() > word2.length() && word1.startsWith(word2)) {
                return "";  // Invalid: longer word before its prefix
            }

            // Find first differing character
            for (int j = 0; j < minLen; j++) {
                char c1 = word1.charAt(j);
                char c2 = word2.charAt(j);

                if (c1 != c2) {
                    // c1 comes before c2 in alien alphabet
                    graph.get(c1).add(c2);
                    break;  // Only need first difference
                }
            }
        }

        // Step 3: DFS with cycle detection
        int[] state = new int[26];
        Stack<Character> stack = new Stack<>();

        for (char c : graph.keySet()) {
            if (state[c - 'a'] == WHITE) {
                if (!dfs(c, state, stack, graph)) {
                    return "";  // Cycle detected
                }
            }
        }

        // Step 4: Build result from stack (reverse topological order)
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    private boolean dfs(char node, int[] state, Stack<Character> stack,
                        Map<Character, Set<Character>> graph) {
        state[node - 'a'] = GRAY;  // Mark as currently exploring

        // Visit all neighbors
        for (char neighbor : graph.get(node)) {
            if (state[neighbor - 'a'] == GRAY) {
                return false;  // Cycle detected! (back edge to gray node)
            }

            if (state[neighbor - 'a'] == WHITE) {
                if (!dfs(neighbor, state, stack, graph)) {
                    return false;  // Cycle found in subtree
                }
            }
            // If BLACK, skip (already processed)
        }

        state[node - 'a'] = BLACK;  // Mark as finished
        stack.push(node);  // Post-order: push after visiting all children
        return true;  // No cycle found
    }
}