269. Alien Dictionary - Explanation

Description

There is a new alien language that uses the English alphabet, but the order of the letters is unknown.

You are given a list of strings words from the alien language's dictionary. It is claimed that the strings in words are sorted lexicographically by the rules of this new language.

If this claim is incorrect, and the given arrangement of strings in words cannot correspond to any order of letters, return "".

Otherwise, 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 are multiple solutions, return any of them.

A string a is lexicographically smaller than a string b if either of the following is true:

The first letter where they differ is smaller in a than in b.
a is a prefix of b and a.length < b.length.

Example 1:

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

Output: "zo"

Explanation:
From "z" and "o", we know 'z' < 'o', so return "zo".

Example 2:

Input: words = ["hrn","hrf","er","enn","rfnn"]

Output: "hernf"

Explanation:

from "hrn" and "hrf", we know 'n' < 'f'
from "hrf" and "er", we know 'h' < 'e'
from "er" and "enn", we know 'r' < 'n'
from "enn" and "rfnn" we know 'e' < 'r'
so one possible solution is "hernf"

Example 3:

Input: words = ["abc","ab"]

Output: ""

Explanation:
The second word is a prefix of the first word, but the first word appears before the second. This is impossible in a valid lexicographical ordering, so return "".

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters.

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(N + V + E) time and O(V + E) space, where N is the sum of the lengths of all the strings, V is the number of unique characters (vertices), and E is the number of edges.

Hint 1

Can you think of this as a graph problem? Characters from a through z are nodes. What could the edges represent here? How can you create edges from the given words? Perhaps you should try comparing two adjacent words.

Hint 2

The relative ordering of the characters can be treated as edges. For example, consider the words ordered as ["ape", "apple"]. "ape" comes before "apple", which indicates that 'e' is a predecessor of 'p'. Therefore, there is a directed edge e -> p, and this dependency should be valid across all the words. In this way, we can build an adjacency list by comparing adjacent words. Can you think of an algorithm that is suitable to find a valid ordering?

Hint 3

We can use Topological Sort to ensure every node appears after its predecessor. Using DFS, we traverse the graph built from the adjacency list. A visited map tracks nodes in the current DFS path: False means not in the path, and True means in the path. If any DFS call returns True, it indicates a cycle and we return immediately. How do we extract the ordering from this DFS?

Hint 4

When we visit a node and its children and don't find a cycle, we mark the node as False in the map and append it to the result, treating this as a post-order traversal. If we find a cycle, we return an empty string; otherwise, we return the result list.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Graph Representation - Building adjacency lists from relationships between elements
Topological Sort - Ordering nodes in a directed acyclic graph based on dependencies
Depth First Search (DFS) - Recursive graph traversal with cycle detection using visited states
Kahn's Algorithm (BFS) - Iterative topological sort using in-degree counting
String Comparison - Extracting ordering rules by comparing adjacent strings character by character

1. Depth First Search

Intuition

The words are already sorted in an unknown alphabet order.
So when you compare two adjacent words, the first position where they differ tells you a rule about letter order:

If w1[j] != w2[j], then w1[j] must come before w2[j] in the alien alphabet (w1[j] -> w2[j]).

All these rules form a directed graph (letters = nodes, “comes before” = directed edge).
Now the problem becomes: find a topological ordering of this graph.

DFS helps in two ways:

Build the ordering (postorder append).
Detect cycles (if there’s a cycle, no valid alphabet exists).

Also, special invalid case:

If w1 is longer but w2 is a prefix of w1 (like "abc" before "ab"), that's impossible - return "".

Algorithm

Build a graph with every unique character as a node.
For each pair of adjacent words:
- If w1 starts with w2 and len(w1) > len(w2), return "".
- Otherwise, find the first differing character and add edge w1[j] -> w2[j].
Run dfs from every character:
- Use 3-state tracking (commonly done with a map):
  - visiting (in current recursion path) - cycle if seen again
  - visited (fully processed) - skip
  - unvisited
- After exploring all neighbors, add the character to result (postorder).
Reverse the result list to get the alien alphabet order.
If any dfs finds a cycle, return ""; else return the joined string.

class Solution:
    def foreignDictionary(self, words: List[str]) -> str:
        adj = {c: set() for w in words for c in w}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            minLen = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
                return ""
            for j in range(minLen):
                if w1[j] != w2[j]:
                    adj[w1[j]].add(w2[j])
                    break

        visited = {}
        res = []

        def dfs(char):
            if char in visited:
                return visited[char]

            visited[char] = True

            for neighChar in adj[char]:
                if dfs(neighChar):
                    return True

            visited[char] = False
            res.append(char)

        for char in adj:
            if dfs(char):
                return ""

        res.reverse()
        return "".join(res)

public class Solution {
    private Map<Character, Set<Character>> adj;
    private Map<Character, Boolean> visited;
    private List<Character> result;

    public String foreignDictionary(String[] words) {
        adj = new HashMap<>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                adj.putIfAbsent(c, new HashSet<>());
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i + 1];
            int minLen = Math.min(w1.length(), w2.length());
            if (w1.length() > w2.length() &&
                w1.substring(0, minLen).equals(w2.substring(0, minLen))) {
                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;
                }
            }
        }

        visited = new HashMap<>();
        result = new ArrayList<>();
        for (char c : adj.keySet()) {
            if (dfs(c)) {
                return "";
            }
        }

        Collections.reverse(result);
        StringBuilder sb = new StringBuilder();
        for (char c : result) {
            sb.append(c);
        }
        return sb.toString();
    }

    private boolean dfs(char ch) {
        if (visited.containsKey(ch)) {
            return visited.get(ch);
        }

        visited.put(ch, true);
        for (char next : adj.get(ch)) {
            if (dfs(next)) {
                return true;
            }
        }
        visited.put(ch, false);
        result.add(ch);
        return false;
    }
}

class Solution {
public:
    unordered_map<char, unordered_set<char>> adj;
    unordered_map<char, bool> visited;
    string result;

    string foreignDictionary(vector<string>& words) {
        for (const auto& word : words) {
            for (char ch : word) {
                adj[ch];
            }
        }

        for (size_t i = 0; i < words.size() - 1; ++i) {
            const string& w1 = words[i], & w2 = words[i + 1];
            size_t minLen = min(w1.length(), w2.length());
            if (w1.length() > w2.length() &&
                w1.substr(0, minLen) == w2.substr(0, minLen)) {
                return "";
            }
            for (size_t j = 0; j < minLen; ++j) {
                if (w1[j] != w2[j]) {
                    adj[w1[j]].insert(w2[j]);
                    break;
                }
            }
        }

        for (const auto& pair : adj) {
            if (dfs(pair.first)) {
                return "";
            }
        }

        reverse(result.begin(), result.end());
        return result;
    }

    bool dfs(char ch) {
        if (visited.find(ch) != visited.end()) {
            return visited[ch];
        }

        visited[ch] = true;
        for (char next : adj[ch]) {
            if (dfs(next)) {
                return true;
            }
        }
        visited[ch] = false;
        result.push_back(ch);
        return false;
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @returns {string}
     */
    foreignDictionary(words) {
        const adj = {};
        for (const word of words) {
            for (const char of word) {
                adj[char] = new Set();
            }
        }

        for (let i = 0; i < words.length - 1; i++) {
            const w1 = words[i];
            const w2 = words[i + 1];
            const minLen = Math.min(w1.length, w2.length);
            if (
                w1.length > w2.length &&
                w1.slice(0, minLen) === w2.slice(0, minLen)
            ) {
                return '';
            }
            for (let j = 0; j < minLen; j++) {
                if (w1[j] !== w2[j]) {
                    adj[w1[j]].add(w2[j]);
                    break;
                }
            }
        }

        const visited = {};
        const res = [];

        const dfs = (char) => {
            if (char in visited) return visited[char];
            visited[char] = true;

            for (const neighChar of adj[char]) {
                if (dfs(neighChar)) return true;
            }

            visited[char] = false;
            res.push(char);
            return false;
        };

        for (const char in adj) {
            if (dfs(char)) return '';
        }

        res.reverse();
        return res.join('');
    }
}

public class Solution {
    private Dictionary<char, HashSet<char>> adj;
    private Dictionary<char, bool> visited;
    private List<char> result;

    public string foreignDictionary(string[] words) {
        adj = new Dictionary<char, HashSet<char>>();
        foreach (var word in words) {
            foreach (var c in word) {
                if (!adj.ContainsKey(c)) {
                    adj[c] = new HashSet<char>();
                }
            }
        }

        for (int i = 0; i < words.Length - 1; i++) {
            var w1 = words[i];
            var w2 = words[i + 1];
            int minLen = Math.Min(w1.Length, w2.Length);
            if (w1.Length > w2.Length && w1.Substring(0, minLen) == w2.Substring(0, minLen)) {
                return "";
            }
            for (int j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    adj[w1[j]].Add(w2[j]);
                    break;
                }
            }
        }

        visited = new Dictionary<char, bool>();
        result = new List<char>();
        foreach (var c in adj.Keys) {
            if (dfs(c)) {
                return "";
            }
        }

        result.Reverse();
        var sb = new StringBuilder();
        foreach (var c in result) {
            sb.Append(c);
        }
        return sb.ToString();
    }

    private bool dfs(char ch) {
        if (visited.ContainsKey(ch)) {
            return visited[ch];
        }

        visited[ch] = true;
        foreach (var next in adj[ch]) {
            if (dfs(next)) {
                return true;
            }
        }
        visited[ch] = false;
        result.Add(ch);
        return false;
    }
}

func foreignDictionary(words []string) string {
    adj := make(map[rune]map[rune]struct{})
    for _, w := range words {
        for _, c := range w {
            if _, exists := adj[c]; !exists {
                adj[c] = make(map[rune]struct{})
            }
        }
    }

    for i := 0; i < len(words)-1; i++ {
        w1, w2 := words[i], words[i+1]
        minLen := len(w1)
        if len(w2) < minLen {
            minLen = len(w2)
        }
        if len(w1) > len(w2) && w1[:minLen] == w2[:minLen] {
            return ""
        }
        for j := 0; j < minLen; j++ {
            if w1[j] != w2[j] {
                adj[rune(w1[j])][rune(w2[j])] = struct{}{}
                break
            }
        }
    }

    visited := make(map[rune]int)
    var res []rune

    var dfs func(char rune) bool
    dfs = func(char rune) bool {
        if status, exists := visited[char]; exists {
            return status == 1
        }

        visited[char] = 1

        for neighChar := range adj[char] {
            if dfs(neighChar) {
                return true
            }
        }

        visited[char] = -1
        res = append(res, char)
        return false
    }

    for char := range adj {
        if dfs(char) {
            return ""
        }
    }

    var result []byte
    for i := len(res) - 1; i >= 0; i-- {
        result = append(result, byte(res[i]))
    }

    return string(result)
}

class Solution {
    fun foreignDictionary(words: Array<String>): String {
        val adj = HashMap<Char, HashSet<Char>>()
        for (w in words) {
            for (c in w) {
                adj.putIfAbsent(c, hashSetOf())
            }
        }

        for (i in 0 until words.size - 1) {
            val w1 = words[i]
            val w2 = words[i + 1]
            val minLen = minOf(w1.length, w2.length)
            if (w1.length > w2.length &&
                w1.substring(0, minLen) == w2.substring(0, minLen)) {
                return ""
            }
            for (j in 0 until minLen) {
                if (w1[j] != w2[j]) {
                    adj[w1[j]]?.add(w2[j])
                    break
                }
            }
        }

        val visited = HashMap<Char, Int>()
        val res = mutableListOf<Char>()

        fun dfs(char: Char): Boolean {
            if (char in visited) {
                return visited[char] == 1
            }

            visited[char] = 1

            for (neighChar in adj[char] ?: emptySet()) {
                if (dfs(neighChar)) {
                    return true
                }
            }

            visited[char] = -1
            res.add(char)
            return false
        }

        for (char in adj.keys) {
            if (dfs(char)) {
                return ""
            }
        }

        return res.reversed().joinToString("")
    }
}

class Solution {
    func foreignDictionary(_ words: [String]) -> String {
        var adj = [Character: Set<Character>]()
        for word in words {
            for char in word {
                if adj[char] == nil {
                    adj[char] = Set<Character>()
                }
            }
        }

        for i in 0..<words.count - 1 {
            let w1 = words[i]
            let w2 = words[i + 1]
            let minLen = min(w1.count, w2.count)
            if w1.count > w2.count && String(w1.prefix(minLen)) == String(w2.prefix(minLen)) {
                return ""
            }
            for j in 0..<minLen {
                let index1 = w1.index(w1.startIndex, offsetBy: j)
                let index2 = w2.index(w2.startIndex, offsetBy: j)
                if w1[index1] != w2[index2] {
                    adj[w1[index1]]?.insert(w2[index2])
                    break
                }
            }
        }

        var visited = [Character: Bool]()
        var res = [Character]()

        func dfs(_ char: Character) -> Bool {
            if let flag = visited[char] {
                return flag
            }
            visited[char] = true
            for neigh in adj[char]! {
                if dfs(neigh) {
                    return true
                }
            }
            visited[char] = false
            res.append(char)
            return false
        }

        for char in adj.keys {
            if dfs(char) {
                return ""
            }
        }

        res.reverse()
        return String(res)
    }
}

impl Solution {
    pub fn foreign_dictionary(words: Vec<String>) -> String {
        let mut adj: HashMap<u8, HashSet<u8>> = HashMap::new();
        for word in &words {
            for &c in word.as_bytes() {
                adj.entry(c).or_insert_with(HashSet::new);
            }
        }

        for i in 0..words.len() - 1 {
            let w1 = words[i].as_bytes();
            let w2 = words[i + 1].as_bytes();
            let min_len = w1.len().min(w2.len());
            if w1.len() > w2.len() && w1[..min_len] == w2[..min_len] {
                return String::new();
            }
            for j in 0..min_len {
                if w1[j] != w2[j] {
                    adj.get_mut(&w1[j]).unwrap().insert(w2[j]);
                    break;
                }
            }
        }

        let mut visited: HashMap<u8, bool> = HashMap::new();
        let mut result: Vec<u8> = Vec::new();

        fn dfs(
            ch: u8,
            adj: &HashMap<u8, HashSet<u8>>,
            visited: &mut HashMap<u8, bool>,
            result: &mut Vec<u8>,
        ) -> bool {
            if let Some(&flag) = visited.get(&ch) {
                return flag;
            }
            visited.insert(ch, true);
            if let Some(neighbors) = adj.get(&ch) {
                for &next in neighbors {
                    if dfs(next, adj, visited, result) {
                        return true;
                    }
                }
            }
            visited.insert(ch, false);
            result.push(ch);
            false
        }

        let keys: Vec<u8> = adj.keys().copied().collect();
        for c in keys {
            if dfs(c, &adj, &mut visited, &mut result) {
                return String::new();
            }
        }

        result.reverse();
        String::from_utf8(result).unwrap()
    }
}

Time & Space Complexity

Time complexity: $O(N + V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of unique characters, $E$ is the number of edges and $N$ is the sum of lengths of all the strings.

2. Topological Sort (Kahn's Algorithm)

Intuition

From the sorted alien words, each pair of adjacent words gives you a letter-order rule at the first mismatching character:

if w1[j] != w2[j], then w1[j] -> w2[j] (meaning w1[j] comes before w2[j]).

These rules form a directed graph. The alien alphabet is just a topological ordering of this graph.

Kahn's algorithm (BFS topological sort) works by:

Counting how many prerequisites each letter has (indegree).
Always picking letters with indegree = 0 (no unmet prerequisites) and "removing" them from the graph.

If there's a cycle, some letters will never reach indegree 0, so we won't be able to output all letters.

Also invalid input case:

If a longer word comes before its own prefix (e.g., "abc" before "ab"), ordering is impossible.

Algorithm

Create a graph node for every unique character in all words.
For each adjacent pair (w1, w2):
- If w1 starts with w2 and len(w1) > len(w2), return "".
- Find the first index j where they differ and add edge w1[j] -> w2[j] (only once).
- Increase indegree[w2[j]] when you add a new edge.
Push all characters with indegree = 0 into a queue.
While the queue is not empty:
- Pop a character, add it to the answer.
- For each neighbor, decrement its indegree.
- If a neighbor becomes 0, push it into the queue.
If the answer contains fewer characters than total unique characters, a cycle exists - return "".
Otherwise, join the answer list and return it.

class Solution:
    def foreignDictionary(self, words):
        adj = {c: set() for w in words for c in w}
        indegree = {c: 0 for c in adj}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            minLen = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
                return ""
            for j in range(minLen):
                if w1[j] != w2[j]:
                    if w2[j] not in adj[w1[j]]:
                        adj[w1[j]].add(w2[j])
                        indegree[w2[j]] += 1
                    break

        q = deque([c for c in indegree if indegree[c] == 0])
        res = []

        while q:
            char = q.popleft()
            res.append(char)
            for neighbor in adj[char]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    q.append(neighbor)

        if len(res) != len(indegree):
            return ""

        return "".join(res)

public class Solution {
    public String foreignDictionary(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();

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

        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());
            if (w1.length() > w2.length() &&
                w1.substring(0, minLen).equals(w2.substring(0, minLen))) {
                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.put(w2.charAt(j),
                                     indegree.get(w2.charAt(j)) + 1);
                    }
                    break;
                }
            }
        }

        Queue<Character> q = new LinkedList<>();
        for (char c : indegree.keySet()) {
            if (indegree.get(c) == 0) {
                q.offer(c);
            }
        }

        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()) {
            char char_ = q.poll();
            res.append(char_);
            for (char neighbor : adj.get(char_)) {
                indegree.put(neighbor, indegree.get(neighbor) - 1);
                if (indegree.get(neighbor) == 0) {
                    q.offer(neighbor);
                }
            }
        }

        if (res.length() != indegree.size()) {
            return "";
        }

        return res.toString();
    }
}

class Solution {
public:
    string foreignDictionary(vector<string>& words) {
        unordered_map<char, unordered_set<char>> adj;
        unordered_map<char, int> indegree;
        for (string w : words) {
            for (char c : w) {
                adj[c] = unordered_set<char>();
                indegree[c] = 0;
            }
        }

        for (int i = 0; i < words.size() - 1; i++) {
            string w1 = words[i], w2 = words[i + 1];
            int minLen = min(w1.size(), w2.size());
            if (w1.size() > w2.size() &&
                w1.substr(0, minLen) == w2.substr(0, minLen)) {
                return "";
            }
            for (int j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    if (!adj[w1[j]].count(w2[j])) {
                        adj[w1[j]].insert(w2[j]);
                        indegree[w2[j]]++;
                    }
                    break;
                }
            }
        }

        queue<char> q;
        for (auto &[c, deg] : indegree) {
            if (deg == 0) {
                q.push(c);
            }
        }

        string res;
        while (!q.empty()) {
            char char_ = q.front();
            q.pop();
            res += char_;
            for (char neighbor : adj[char_]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return res.size() == indegree.size() ? res : "";
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @returns {string}
     */
    foreignDictionary(words) {
        let adj = {};
        let indegree = {};
        for (let w of words) {
            for (let c of w) {
                adj[c] = new Set();
                indegree[c] = 0;
            }
        }

        for (let i = 0; i < words.length - 1; i++) {
            let w1 = words[i],
                w2 = words[i + 1];
            let minLen = Math.min(w1.length, w2.length);
            if (
                w1.length > w2.length &&
                w1.slice(0, minLen) === w2.slice(0, minLen)
            ) {
                return '';
            }
            for (let j = 0; j < minLen; j++) {
                if (w1[j] !== w2[j]) {
                    if (!adj[w1[j]].has(w2[j])) {
                        adj[w1[j]].add(w2[j]);
                        indegree[w2[j]] += 1;
                    }
                    break;
                }
            }
        }

        let q = new Queue();
        for (let c in indegree) {
            if (indegree[c] === 0) {
                q.push(c);
            }
        }

        let res = [];
        while (!q.isEmpty()) {
            let char = q.pop();
            res.push(char);
            for (let neighbor of adj[char]) {
                indegree[neighbor] -= 1;
                if (indegree[neighbor] === 0) {
                    q.push(neighbor);
                }
            }
        }

        if (res.length !== Object.keys(indegree).length) {
            return '';
        }

        return res.join('');
    }
}

public class Solution {
    public string foreignDictionary(string[] words) {
        var adj = new Dictionary<char, HashSet<char>>();
        var indegree = new Dictionary<char, int>();

        foreach (var word in words) {
            foreach (var c in word) {
                if (!adj.ContainsKey(c)) {
                    adj[c] = new HashSet<char>();
                }
                if (!indegree.ContainsKey(c)) {
                    indegree[c] = 0;
                }
            }
        }

        for (int i = 0; i < words.Length - 1; i++) {
            var w1 = words[i];
            var w2 = words[i + 1];
            int minLen = Math.Min(w1.Length, w2.Length);
            if (w1.Length > w2.Length &&
                w1.Substring(0, minLen) == w2.Substring(0, minLen)) {
                return "";
            }
            for (int j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    if (!adj[w1[j]].Contains(w2[j])) {
                        adj[w1[j]].Add(w2[j]);
                        indegree[w2[j]]++;
                    }
                    break;
                }
            }
        }

        var q = new Queue<char>();
        foreach (var c in indegree.Keys) {
            if (indegree[c] == 0) {
                q.Enqueue(c);
            }
        }

        var res = new StringBuilder();
        while (q.Count > 0) {
            var char_ = q.Dequeue();
            res.Append(char_);
            foreach (var neighbor in adj[char_]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.Enqueue(neighbor);
                }
            }
        }

        if (res.Length != indegree.Count) {
            return "";
        }

        return res.ToString();
    }
}

func foreignDictionary(words []string) string {
    adj := make(map[byte]map[byte]struct{})
    indegree := make(map[byte]int)

    for _, word := range words {
        for i := 0; i < len(word); i++ {
            char := word[i]
            if _, exists := adj[char]; !exists {
                adj[char] = make(map[byte]struct{})
            }
            indegree[char] = 0
        }
    }

    for i := 0; i < len(words)-1; i++ {
        w1, w2 := words[i], words[i+1]
        minLen := len(w1)
        if len(w2) < minLen {
            minLen = len(w2)
        }

        if len(w1) > len(w2) && w1[:minLen] == w2[:minLen] {
            return ""
        }

        for j := 0; j < minLen; j++ {
            if w1[j] != w2[j] {
                if _, exists := adj[w1[j]][w2[j]]; !exists {
                    adj[w1[j]][w2[j]] = struct{}{}
                    indegree[w2[j]]++
                }
                break
            }
        }
    }

    q := []byte{}
    for char := range indegree {
        if indegree[char] == 0 {
            q = append(q, char)
        }
    }

    res := []byte{}
    for len(q) > 0 {
        char := q[0]
        q = q[1:]
        res = append(res, char)

        for neighbor := range adj[char] {
            indegree[neighbor]--
            if indegree[neighbor] == 0 {
                q = append(q, neighbor)
            }
        }
    }

    if len(res) != len(indegree) {
        return ""
    }

    return string(res)
}

class Solution {
    fun foreignDictionary(words: Array<String>): String {
        val adj = HashMap<Char, HashSet<Char>>()
        val indegree = HashMap<Char, Int>()

        for (word in words) {
            for (c in word) {
                adj.computeIfAbsent(c) { hashSetOf() }
                indegree[c] = 0
            }
        }

        for (i in 0 until words.size - 1) {
            val w1 = words[i]
            val w2 = words[i + 1]
            val minLen = minOf(w1.length, w2.length)

            if (w1.length > w2.length &&
                w1.substring(0, minLen) == w2.substring(0, minLen)) {
                return ""
            }

            for (j in 0 until minLen) {
                if (w1[j] != w2[j]) {
                    if (w2[j] !in adj[w1[j]]!!) {
                        adj[w1[j]]!!.add(w2[j])
                        indegree[w2[j]] = indegree[w2[j]]!! + 1
                    }
                    break
                }
            }
        }

        val q: Queue<Char> = LinkedList()
        for ((char, degree) in indegree) {
            if (degree == 0) {
                q.add(char)
            }
        }

        val res = StringBuilder()
        while (q.isNotEmpty()) {
            val char = q.poll()
            res.append(char)

            for (neighbor in adj[char]!!) {
                indegree[neighbor] = indegree[neighbor]!! - 1
                if (indegree[neighbor] == 0) {
                    q.add(neighbor)
                }
            }
        }

        return if (res.length != indegree.size) "" else res.toString()
    }
}

class Solution {
    func foreignDictionary(_ words: [String]) -> String {
        var adj = [Character: Set<Character>]()
        for word in words {
            for char in word {
                adj[char] = Set<Character>()
            }
        }

        var indegree = [Character: Int]()
        for key in adj.keys {
            indegree[key] = 0
        }

        for i in 0..<words.count - 1 {
            let w1 = words[i]
            let w2 = words[i + 1]
            let minLen = min(w1.count, w2.count)
            if w1.count > w2.count && String(w1.prefix(minLen)) == String(w2.prefix(minLen)) {
                return ""
            }
            let w1Arr = Array(w1)
            let w2Arr = Array(w2)
            for j in 0..<minLen {
                if w1Arr[j] != w2Arr[j] {
                    if !adj[w1Arr[j]]!.contains(w2Arr[j]) {
                        adj[w1Arr[j]]!.insert(w2Arr[j])
                        indegree[w2Arr[j]]! += 1
                    }
                    break
                }
            }
        }

        var q = Deque<Character>()
        for (c, deg) in indegree {
            if deg == 0 {
                q.append(c)
            }
        }

        var res = [Character]()
        while !q.isEmpty {
            let char = q.removeFirst()
            res.append(char)
            for neighbor in adj[char]! {
                indegree[neighbor]! -= 1
                if indegree[neighbor]! == 0 {
                    q.append(neighbor)
                }
            }
        }

        if res.count != indegree.count {
            return ""
        }

        return String(res)
    }
}

impl Solution {
    pub fn foreign_dictionary(words: Vec<String>) -> String {
        let mut adj: HashMap<u8, HashSet<u8>> = HashMap::new();
        let mut indegree: HashMap<u8, i32> = HashMap::new();

        for word in &words {
            for &c in word.as_bytes() {
                adj.entry(c).or_insert_with(HashSet::new);
                indegree.entry(c).or_insert(0);
            }
        }

        for i in 0..words.len() - 1 {
            let w1 = words[i].as_bytes();
            let w2 = words[i + 1].as_bytes();
            let min_len = w1.len().min(w2.len());
            if w1.len() > w2.len() && w1[..min_len] == w2[..min_len] {
                return String::new();
            }
            for j in 0..min_len {
                if w1[j] != w2[j] {
                    if adj.get_mut(&w1[j]).unwrap().insert(w2[j]) {
                        *indegree.get_mut(&w2[j]).unwrap() += 1;
                    }
                    break;
                }
            }
        }

        let mut q: VecDeque<u8> = VecDeque::new();
        for (&c, &deg) in &indegree {
            if deg == 0 {
                q.push_back(c);
            }
        }

        let mut res: Vec<u8> = Vec::new();
        while let Some(ch) = q.pop_front() {
            res.push(ch);
            if let Some(neighbors) = adj.get(&ch) {
                for &neighbor in neighbors {
                    let deg = indegree.get_mut(&neighbor).unwrap();
                    *deg -= 1;
                    if *deg == 0 {
                        q.push_back(neighbor);
                    }
                }
            }
        }

        if res.len() != indegree.len() {
            return String::new();
        }

        String::from_utf8(res).unwrap()
    }
}

Time & Space Complexity

Time complexity: $O(N + V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of unique characters, $E$ is the number of edges and $N$ is the sum of lengths of all the strings.

Common Pitfalls

Missing the Invalid Prefix Case

When a longer word appears before its own prefix (e.g., "abc" before "ab"), this is an invalid ordering that cannot exist in any alphabet. Failing to detect this case and return an empty string leads to incorrect results or undefined behavior.

Only Comparing Adjacent Words Partially

The ordering information comes from the first differing character between adjacent words. A common mistake is comparing all differing characters or only comparing the first characters. You must find the first position where characters differ and extract exactly one edge from that comparison.

Not Including All Characters in the Result

Characters that appear in the words but have no ordering constraints (no incoming or outgoing edges) must still appear in the final alphabet. Forgetting to initialize nodes for all unique characters causes some letters to be missing from the output.

Incorrect Cycle Detection in DFS

The three-state visited tracking (unvisited, visiting, visited) is crucial for detecting cycles. Using only two states (visited/unvisited) cannot distinguish between a back edge (cycle) and a cross edge (already processed node). This leads to either false cycle detection or missing actual cycles.

Adding Duplicate Edges

When the same character pair appears from multiple adjacent word comparisons, adding duplicate edges inflates the indegree count in Kahn's algorithm, preventing nodes from ever reaching zero indegree. Use a set to track existing edges before adding new ones.