Alien Dictionary

Description

There is a new alien language that uses the Latin 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 are sorted lexicographically according to the rules of this new language.

Derive the order of letters in this language and return it as a string of unique letters. If no valid ordering exists, return an empty string "". If there are multiple valid orderings, return any of them.

Examples

Example 1

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]

Output: "wertf"

Explanation:

Comparing "wrt" and "wrf": first difference at index 2 → t comes before f.
Comparing "wrf" and "er": first difference at index 0 → w comes before e.
Comparing "er" and "ett": first difference at index 1 → r comes before t.
Comparing "ett" and "rftt": first difference at index 0 → e comes before r.

Combining these rules: w → e → r → t → f, giving the order "wertf".

Example 2

Input: words = ["z", "x"]

Output: "zx"

Explanation: From the ordering, "z" comes before "x", so z precedes x in the alien alphabet.

Example 3

Input: words = ["z", "x", "z"]

Output: ""

Explanation: From "z" before "x" we get z → x. From "x" before "z" we get x → z. This creates a cycle (z → x → z), so no valid ordering exists. Return an empty string.

Constraints

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 100
words[i] consists of only lowercase English letters
All the strings in words are unique

Editorial

Approach 1 - DFS Topological Sort

Intuition

The words are already sorted according to the alien alphabet. This is the critical insight — we don't need to sort anything; the ordering is given to us implicitly through the word list. Our job is to decode it.

Think about how a regular dictionary works: "cat" comes before "car" because at the first position where they differ (index 2), 't' comes before 'r' in the English alphabet. We can reverse this logic. If someone tells us "cat" is listed before "car" in their alien dictionary, we can infer that 't' must come before 'r' in their alphabet.

By comparing every pair of adjacent words in the list, we extract one ordering rule per pair (from the first position where the words differ). Each rule is a directed edge: if character u comes before character v, draw an arrow u → v.

All these arrows form a directed graph. Finding a valid alphabet order means finding an ordering of all characters such that every arrow points forward — that is, a topological sort of the graph.

We use DFS-based topological sort: perform DFS from every unvisited character, and after all descendants of a character have been fully explored, append that character to the result. Because DFS finishes deeper nodes first, the result comes out in reverse topological order — we simply reverse it at the end.

DFS also lets us detect cycles using a three-state visited system (unvisited, visiting, visited). If we encounter a node that is currently being visited (i.e., it's on the recursion stack), a cycle exists and no valid ordering is possible — return "".

Another edge case: if a longer word appears before its own prefix (e.g., "abc" before "ab"), this is invalid in any alphabet. We must check for this and return "" immediately.

Step-by-Step Explanation

Let's trace through with words = ["wrt", "wrf", "er", "ett", "rftt"]:

Step 1 — Initialize the graph: Collect all unique characters: {w, r, t, f, e}. Create an adjacency list with an empty set of neighbors for each character.

Step 2 — Compare "wrt" vs "wrf": Characters at index 0: w == w (same). Index 1: r == r (same). Index 2: t ≠ f → Add edge t → f.

Step 3 — Compare "wrf" vs "er": Index 0: w ≠ e → Add edge w → e.

Step 4 — Compare "er" vs "ett": Index 0: e == e (same). Index 1: r ≠ t → Add edge r → t.

Step 5 — Compare "ett" vs "rftt": Index 0: e ≠ r → Add edge e → r.

Step 6 — Graph built: w → {e}, e → {r}, r → {t}, t → {f}. This is a clean chain with no cycles.

Step 7 — Run DFS from each unvisited node: Start DFS from 'w'. It traverses w → e → r → t → f. Post-order appends: f, t, r, e, w.

Step 8 — Reverse post-order result: [f, t, r, e, w] → [w, e, r, t, f].

Step 9 — Return "wertf".

DFS Topological Sort — Building and Traversing the Dependency Graph — Watch how we extract ordering rules from adjacent word pairs, build a directed graph, and perform DFS to produce a valid topological ordering of the alien alphabet.

Algorithm

Build an adjacency list: for each unique character across all words, initialize an empty set of neighbors.
For each pair of adjacent words (words[i], words[i+1]):
- If words[i] is longer than words[i+1] and words[i+1] is a prefix of words[i], return "" (invalid).
- Find the first index j where words[i][j] != words[i+1][j]. Add a directed edge from words[i][j] to words[i+1][j]. Break after the first difference.
Run DFS from every unvisited character. Use three states: unvisited, visiting (in current recursion path), visited (fully processed).
If any DFS encounters a node in the 'visiting' state, a cycle exists — return "".
After DFS finishes for a node (all neighbors fully explored), append it to the result list (post-order).
Reverse the result list and join it into a string. Return it.

Code

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> adj;
        
        // Initialize graph with all unique characters
        for (const string& word : words) {
            for (char c : word) {
                adj[c]; // creates entry if not exists
            }
        }
        
        // Build edges from adjacent word pairs
        for (int i = 0; i + 1 < words.size(); i++) {
            string& w1 = words[i];
            string& w2 = words[i + 1];
            int minLen = min(w1.size(), w2.size());
            
            // Invalid: longer word before its own prefix
            if (w1.size() > w2.size() && w1.substr(0, minLen) == w2) {
                return "";
            }
            
            for (int j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    adj[w1[j]].insert(w2[j]);
                    break;
                }
            }
        }
        
        // DFS topological sort with cycle detection
        // 0 = unvisited, 1 = visiting, 2 = visited
        unordered_map<char, int> visited;
        string result;
        
        function<bool(char)> dfs = [&](char c) -> bool {
            if (visited.count(c)) {
                return visited[c] == 1; // cycle if visiting
            }
            visited[c] = 1; // mark visiting
            
            for (char neighbor : adj[c]) {
                if (dfs(neighbor)) return true; // cycle
            }
            
            visited[c] = 2; // mark visited
            result += c;
            return false;
        };
        
        for (auto& [c, _] : adj) {
            if (dfs(c)) return ""; // cycle detected
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        # Initialize graph with all unique characters
        adj = {c: set() for word in words for c in word}
        
        # Build edges from adjacent word pairs
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))
            
            # Invalid: longer word before its own prefix
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""
            
            for j in range(min_len):
                if w1[j] != w2[j]:
                    adj[w1[j]].add(w2[j])
                    break
        
        # DFS topological sort with cycle detection
        # visited[c] = True means visiting, False means visited
        visited = {}
        result = []
        
        def dfs(char: str) -> bool:
            if char in visited:
                return visited[char]  # True = cycle
            
            visited[char] = True  # mark as visiting
            
            for neighbor in adj[char]:
                if dfs(neighbor):
                    return True  # cycle detected
            
            visited[char] = False  # mark as visited
            result.append(char)
            return False
        
        for c in adj:
            if dfs(c):
                return ""  # cycle detected
        
        result.reverse()
        return "".join(result)

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        
        // Initialize graph with all unique characters
        for (String word : words) {
            for (char c : word.toCharArray()) {
                adj.putIfAbsent(c, new HashSet<>());
            }
        }
        
        // Build edges from adjacent word pairs
        for (int i = 0; i + 1 < words.length; i++) {
            String w1 = words[i], w2 = words[i + 1];
            int minLen = Math.min(w1.length(), w2.length());
            
            // Invalid: longer word before its own prefix
            if (w1.length() > w2.length() && w1.startsWith(w2)) {
                return "";
            }
            
            for (int j = 0; j < minLen; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    adj.get(w1.charAt(j)).add(w2.charAt(j));
                    break;
                }
            }
        }
        
        // DFS topological sort with cycle detection
        // 0 = unvisited, 1 = visiting, 2 = visited
        Map<Character, Integer> visited = new HashMap<>();
        StringBuilder result = new StringBuilder();
        
        for (char c : adj.keySet()) {
            if (hasCycle(c, adj, visited, result)) {
                return "";
            }
        }
        
        return result.reverse().toString();
    }
    
    private boolean hasCycle(char c, Map<Character, Set<Character>> adj,
                             Map<Character, Integer> visited, StringBuilder result) {
        if (visited.containsKey(c)) {
            return visited.get(c) == 1; // cycle if visiting
        }
        
        visited.put(c, 1); // mark visiting
        
        for (char neighbor : adj.get(c)) {
            if (hasCycle(neighbor, adj, visited, result)) {
                return true;
            }
        }
        
        visited.put(c, 2); // mark visited
        result.append(c);
        return false;
    }
}

Complexity Analysis

Time Complexity: O(C)

Where C is the total number of characters across all words. Building the graph requires comparing adjacent words, which processes each character at most once — O(C). The DFS traversal visits each unique character and edge once — O(V + E), where V ≤ 26 and E ≤ V². Since V is bounded by 26, the graph operations are O(1) in theory, making the overall complexity O(C).

Space Complexity: O(1) or O(V + E)

The adjacency list, visited map, and result list all use space proportional to the number of unique characters (at most 26) and edges (at most 26²). Since these are bounded by the alphabet size, it is O(1) if we consider the alphabet fixed, or O(V + E) in general.

Why This Approach Is Not Efficient

The DFS approach is correct and has optimal time complexity. However, it relies on recursion, which means it uses the call stack. For very deep recursion paths (though bounded by 26 here), this could be a concern in languages with limited stack space.

More importantly, DFS-based topological sort produces results in reverse order, requiring an explicit reversal at the end. The three-state cycle detection, while correct, can be tricky to implement and debug.

An alternative is Kahn's Algorithm (BFS-based topological sort), which builds the result in forward order naturally, detects cycles by counting processed nodes, and uses an explicit queue instead of recursion. It is often considered easier to reason about and less error-prone in interview settings.

Optimal Approach - BFS Topological Sort (Kahn's Algorithm)

Intuition

Kahn's Algorithm approaches topological sort from the opposite direction compared to DFS. Instead of diving deep and building the order backwards, it works forwards: start with characters that have no prerequisites (in-degree = 0) and peel them off layer by layer.

Imagine organizing a group project where some tasks depend on others. You start with tasks that have zero dependencies, complete them, and cross them off. This might unlock new tasks whose only dependencies were the ones you just finished. You keep going until all tasks are done — or you discover that some tasks form a circular dependency and can never be started.

In our graph, each character's in-degree counts how many characters must come before it. Characters with in-degree 0 have no constraints pushing them later — they can safely go first. After placing one such character, we remove its outgoing edges (decreasing neighbors' in-degrees). If a neighbor's in-degree drops to 0, it becomes eligible to be placed next.

Cycle detection is elegant: if we finish the BFS but haven't placed all characters, some characters are stuck with in-degree > 0 — they're trapped in a cycle. We return "".

Step-by-Step Explanation

Let's trace through with words = ["wrt", "wrf", "er", "ett", "rftt"]:

Step 1 — Build Graph: Same as before. Edges: t→f, w→e, r→t, e→r.

Step 2 — Compute In-Degrees: w:0, e:1 (from w), r:1 (from e), t:1 (from r), f:1 (from t).

Step 3 — Initialize Queue: Only 'w' has in-degree 0. Queue = [w]. Result = [].

Step 4 — Process 'w': Dequeue 'w', append to result. Remove edge w→e, so e's in-degree drops from 1 to 0. Enqueue 'e'. Queue = [e]. Result = [w].

Step 5 — Process 'e': Dequeue 'e', append to result. Remove edge e→r, so r's in-degree drops to 0. Enqueue 'r'. Queue = [r]. Result = [w, e].

Step 6 — Process 'r': Dequeue 'r', append to result. Remove edge r→t, so t's in-degree drops to 0. Enqueue 't'. Queue = [t]. Result = [w, e, r].

Step 7 — Process 't': Dequeue 't', append to result. Remove edge t→f, so f's in-degree drops to 0. Enqueue 'f'. Queue = [f]. Result = [w, e, r, t].

Step 8 — Process 'f': Dequeue 'f', append to result. No outgoing edges. Queue empty. Result = [w, e, r, t, f].

Step 9 — Validate: We placed 5 characters and there are 5 unique characters total. No cycle. Return "wertf".

Kahn's Algorithm — BFS Layer-by-Layer Topological Ordering — Watch how Kahn's algorithm peels off characters with zero in-degree layer by layer, building the alien alphabet order from left to right without recursion.

Algorithm

Build an adjacency list and initialize an in-degree map for every unique character across all words.
For each pair of adjacent words (words[i], words[i+1]):
- Check for the invalid prefix case: if words[i] is longer and words[i+1] is a prefix of it, return "".
- Find the first differing character position j. Add an edge words[i][j] → words[i+1][j] (only if not already present). Increment in-degree of words[i+1][j]. Break after the first difference.
Push all characters with in-degree 0 into a queue.
While the queue is not empty:
- Dequeue a character, append it to the result.
- For each of its neighbors, decrement their in-degree. If any reaches 0, enqueue it.
After the queue is empty, check: if the result contains fewer characters than the total unique count, a cycle exists — return "". Otherwise, return the result string.

Code

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> adj;
        unordered_map<char, int> indegree;
        
        // Initialize graph with all unique characters
        for (const string& word : words) {
            for (char c : word) {
                adj[c];
                indegree[c] = 0;
            }
        }
        
        // Build edges from adjacent word pairs
        for (int i = 0; i + 1 < words.size(); i++) {
            string& w1 = words[i];
            string& w2 = words[i + 1];
            int minLen = min(w1.size(), w2.size());
            
            if (w1.size() > w2.size() && w1.substr(0, minLen) == w2) {
                return "";
            }
            
            for (int j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    if (adj[w1[j]].find(w2[j]) == adj[w1[j]].end()) {
                        adj[w1[j]].insert(w2[j]);
                        indegree[w2[j]]++;
                    }
                    break;
                }
            }
        }
        
        // BFS topological sort
        queue<char> q;
        for (auto& [c, deg] : indegree) {
            if (deg == 0) q.push(c);
        }
        
        string result;
        while (!q.empty()) {
            char curr = q.front();
            q.pop();
            result += curr;
            
            for (char neighbor : adj[curr]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        return result.size() == indegree.size() ? result : "";
    }
};

from collections import deque

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        # Initialize graph with all unique characters
        adj = {c: set() for word in words for c in word}
        indegree = {c: 0 for c in adj}
        
        # Build edges from adjacent word pairs
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))
            
            # Invalid: longer word before its own prefix
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""
            
            for j in range(min_len):
                if w1[j] != w2[j]:
                    if w2[j] not in adj[w1[j]]:
                        adj[w1[j]].add(w2[j])
                        indegree[w2[j]] += 1
                    break
        
        # BFS topological sort
        queue = deque(c for c in indegree if indegree[c] == 0)
        result = []
        
        while queue:
            char = queue.popleft()
            result.append(char)
            for neighbor in adj[char]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)
        
        if len(result) != len(indegree):
            return ""  # cycle detected
        
        return "".join(result)

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        
        // Initialize graph with all unique characters
        for (String word : words) {
            for (char c : word.toCharArray()) {
                adj.putIfAbsent(c, new HashSet<>());
                indegree.putIfAbsent(c, 0);
            }
        }
        
        // Build edges from adjacent word pairs
        for (int i = 0; i + 1 < words.length; i++) {
            String w1 = words[i], w2 = words[i + 1];
            int minLen = Math.min(w1.length(), w2.length());
            
            if (w1.length() > w2.length() && w1.startsWith(w2)) {
                return "";
            }
            
            for (int j = 0; j < minLen; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    if (!adj.get(w1.charAt(j)).contains(w2.charAt(j))) {
                        adj.get(w1.charAt(j)).add(w2.charAt(j));
                        indegree.merge(w2.charAt(j), 1, Integer::sum);
                    }
                    break;
                }
            }
        }
        
        // BFS topological sort
        Queue<Character> queue = new LinkedList<>();
        for (Map.Entry<Character, Integer> entry : indegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        
        StringBuilder result = new StringBuilder();
        while (!queue.isEmpty()) {
            char curr = queue.poll();
            result.append(curr);
            for (char neighbor : adj.get(curr)) {
                indegree.merge(neighbor, -1, Integer::sum);
                if (indegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return result.length() == indegree.size() ? result.toString() : "";
    }
}

Complexity Analysis

Time Complexity: O(C)

Where C is the total number of characters across all words. Building the graph scans each character at most once — O(C). The BFS processes each unique character and edge once — O(V + E). Since V ≤ 26 and E ≤ V², the graph operations are bounded by a constant. Overall: O(C).

Space Complexity: O(1) or O(V + E)

The adjacency list, in-degree map, queue, and result list are all bounded by the alphabet size (26 characters). V ≤ 26, E ≤ 26² = 676. All auxiliary structures use constant space when the alphabet is fixed. In the general case (arbitrary alphabet), it would be O(V + E).