Log inSign up
hardLeetCodeNot Started

Alien Dictionary

There is a new alien language that uses the English alphabet. Given a list of words from the dictionary sorted lexicographically by the rules of this new language, derive the order of letters in this language.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

There is a new alien language that uses the English alphabet. However, the order among 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 valid order of letters, return "". If there are multiple valid solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

---

### Examples

Example 1: ``text Input: words = ["wrt", "wrf", "er", "ett", "rftt"] Output: "wertf" Explanation: - From "wrt" and "wrf", 't' < 'f'. - From "wrf" and "er", 'w' < 'e'. - From "er" and "ett", 'r' < 't'. - From "ett" and "rftt", 'e' < 'r'. Topological order: 'w' -> 'e' -> 'r' -> 't' -> 'f' => "wertf".

Example 2: ``text Input: words = ["z", "x"] Output: "zx" Explanation: - From "z" and "x", 'z' < 'x'. Output is "zx".

Example 3: ``text Input: words = ["z", "x", "z"] Output: "" Explanation: - 'z' < 'x' and 'x' < 'z'. A cycle exists, which is impossible in a valid dictionary ordering. Return "".

Example 4 (Invalid Prefix): ``text Input: words = ["abc", "ab"] Output: "" Explanation: - "abc" appears before "ab", but "ab" is a prefix of "abc" with shorter length. This violates lexicographical ordering rules.

---

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

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model character lexicographical precedence as a directed graph.
  • Correctly detect invalid dictionary inputs caused by prefix violations.
  • Implement Kahn's algorithm for topological sorting and cycle detection.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Ordered sequence of elements derived from relative comparisons
  • Lexicographical dictionary order from pairwise adjacent words
  • Directed relationship dependencies with potential cycles

Algorithmic Decision Tree:

  • 1. Collect all unique letters in inDegree map with initial 0.
  • 2. For adjacent words (w1, w2), find first mismatch w1[j] != w2[j]. Add edge w1[j] -> w2[j] and increment inDegree[w2[j]].
  • 3. If w1 is longer than w2 and w1.startsWith(w2), return '' immediately.
  • 4. Push all in-degree 0 characters into queue. Pop, append to result, decrement neighbors.
  • 5. If result.length == unique_chars, return result; otherwise return '' (cycle detected).

Connected Patterns:

Course ScheduleCourse Schedule IITopological Sort

1. Exhaustive Permutation Verification

Intuition

Generate all permutations of unique alien letters and check if any permutation satisfies every adjacent word ordering constraint.

Algorithm

  1. Collect all unique characters from the dictionary words.
  2. Generate all permutations of these characters using backtracking.
  3. For each permutation, assign an integer rank to each character.
  4. Verify if words is strictly sorted according to this rank assignment.
  5. If sorted, return the candidate string.
  6. If all permutations fail, return empty string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <unordered_map>
6#include <algorithm>
7
8class Solution {
9 bool isSorted(const std::vector<std::string>& words, const std::string& order) {
10 std::unordered_map<char, int> rank;
11 for (int i = 0; i < order.size(); ++i) rank[order[i]] = i;
12
13 for (int i = 0; i + 1 < words.size(); ++i) {
14 const std::string& w1 = words[i];
15 const std::string& w2 = words[i + 1];
16 int len = std::min(w1.size(), w2.size());
17 bool diff = false;
18 for (int j = 0; j < len; ++j) {
19 if (w1[j] != w2[j]) {
20 if (rank[w1[j]] > rank[w2[j]]) return false;
21 diff = true;
22 break;
23 }
24 }
25 if (!diff && w1.size() > w2.size()) return false;
26 }
27 return true;
28 }
29public:
30 std::string alienOrder(std::vector<std::string>& words) {
31 std::unordered_set<char> charSet;
32 for (const auto& w : words) {
33 for (char c : w) charSet.insert(c);
34 }
35 std::string chars(charSet.begin(), charSet.end());
36 std::sort(chars.begin(), chars.end());
37
38 do {
39 if (isSorted(words, chars)) return chars;
40 } while (std::next_permutation(chars.begin(), chars.end()));
41
42 return "";
43 }
44};
45
46int main() {
47 Solution sol;
48 std::vector<std::string> words = {"z", "x"};
49 std::cout << "Alien order: " << sol.alienOrder(words) << " (Expected: zx)\n";
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(U! * N * L)
  • Space complexity: O(U)

2. DFS Post-Order Traversal with 3-Color Cycle Detection

Intuition

Build directed graph. Use DFS with state tracking (unvisited=0, visiting=1, visited=2) to detect cycles and build reverse topological order.

Algorithm

  1. Initialize adjacency map for all unique characters.
  2. Compare adjacent words to populate edges: u -> v.
  3. If w1.startsWith(w2) and len(w1) > len(w2), return empty string.
  4. Maintain visited map (0 = unvisited, 1 = visiting, 2 = visited).
  5. Define dfs(node):
  6. If visited[node] == 1, return false (cycle).
  7. If visited[node] == 2, return true (already completed).
  8. visited[node] = 1.
  9. For neighbor in adj[node]:
  10. if !dfs(neighbor) return false.
  11. visited[node] = 2.
  12. Append node to postOrder list.
  13. Return true.
  14. Run dfs for all unvisited characters. If cycle detected, return empty string.
  15. Reverse postOrder list and return as string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <unordered_set>
6#include <algorithm>
7
8class Solution {
9 bool dfs(char u, std::unordered_map<char, std::unordered_set<char>>& adj,
10 std::unordered_map<char, int>& visited, std::string& postOrder) {
11 visited[u] = 1; // 1 = visiting (in stack)
12
13 for (char v : adj[u]) {
14 if (visited[v] == 1) return false; // Cycle detected
15 if (visited[v] == 0) {
16 if (!dfs(v, adj, visited, postOrder)) return false;
17 }
18 }
19
20 visited[u] = 2; // 2 = visited
21 postOrder += u;
22 return true;
23 }
24public:
25 std::string alienOrder(std::vector<std::string>& words) {
26 std::unordered_map<char, std::unordered_set<char>> adj;
27 std::unordered_map<char, int> visited;
28
29 // Initialize vertices
30 for (const auto& w : words) {
31 for (char c : w) {
32 adj[c];
33 visited[c] = 0;
34 }
35 }
36
37 // Build edges
38 for (int i = 0; i + 1 < words.size(); ++i) {
39 const std::string& w1 = words[i];
40 const std::string& w2 = words[i + 1];
41 int len = std::min(w1.size(), w2.size());
42 bool diff = false;
43
44 for (int j = 0; j < len; ++j) {
45 if (w1[j] != w2[j]) {
46 adj[w1[j]].insert(w2[j]);
47 diff = true;
48 break;
49 }
50 }
51 // Prefix rule violation: w1 is longer and is a prefix of w2
52 if (!diff && w1.size() > w2.size()) return "";
53 }
54
55 std::string postOrder = "";
56 for (const auto& [c, state] : visited) {
57 if (state == 0) {
58 if (!dfs(c, adj, visited, postOrder)) return "";
59 }
60 }
61
62 std::reverse(postOrder.begin(), postOrder.end());
63 return postOrder;
64 }
65};
66
67int main() {
68 Solution sol;
69 std::vector<std::string> words = {"wrt", "wrf", "er", "ett", "rftt"};
70 std::cout << "Alien order: " << sol.alienOrder(words) << " (Expected: wertf)\n";
71 return 0;
72}

Time & Space Complexity

  • Time complexity: O(C)
  • Space complexity: O(1)

3. Kahn's Algorithm (BFS In-Degree Topological Sort - Industry Standard)

Intuition

Build directed graph and in-degree table. Seed queue with zero in-degree characters. Pop, append to order, decrement neighbor in-degrees.

Algorithm

  1. Initialize inDegree map with 0 for all unique characters, and empty adjacency sets.
  2. Compare adjacent words w1 and w2:
  3. Find first difference w1[j] != w2[j].
  4. If not in set, add edge w1[j] -> w2[j] and increment inDegree[w2[j]].
  5. Prefix violation check: if !diff && w1.length > w2.length, return empty string.
  6. Push all characters with inDegree[c] == 0 into queue.
  7. Initialize result string.
  8. While queue is not empty:
  9. Pop character u, append u to result.
  10. For each neighbor v of u:
  11. inDegree[v]--.
  12. If inDegree[v] == 0, push v to queue.
  13. If result.length == inDegree.size, return result; else return empty string (cycle detected).

Kahn's BFS In-Degree Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Words: ['wrt', 'wrf', 'er', 'ett', 'rftt']
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
w->e, e->r, r->t, t->f
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
t->f, w->e, r->t, e->r
Why this step matters

Words: [wrt, wrf, er, ett, rftt]. Unique: {w, e, r, t, f}.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <unordered_set>
6#include <queue>
7#include <algorithm>
8
9class Solution {
10public:
11 std::string alienOrder(std::vector<std::string>& words) {
12 std::unordered_map<char, std::unordered_set<char>> adj;
13 std::unordered_map<char, int> inDegree;
14
15 // Initialize unique characters with in-degree 0
16 for (const auto& w : words) {
17 for (char c : w) {
18 inDegree[c] = 0;
19 adj[c];
20 }
21 }
22
23 // Build directed graph from adjacent word pairs
24 for (int i = 0; i + 1 < words.size(); ++i) {
25 const std::string& w1 = words[i];
26 const std::string& w2 = words[i + 1];
27 int len = std::min(w1.size(), w2.size());
28 bool diff = false;
29
30 for (int j = 0; j < len; ++j) {
31 if (w1[j] != w2[j]) {
32 char u = w1[j], v = w2[j];
33 if (!adj[u].count(v)) {
34 adj[u].insert(v);
35 inDegree[v]++;
36 }
37 diff = true;
38 break;
39 }
40 }
41 // Invalid prefix check: "abc" before "ab"
42 if (!diff && w1.size() > w2.size()) return "";
43 }
44
45 // Kahn's BFS
46 std::queue<char> q;
47 for (const auto& [c, deg] : inDegree) {
48 if (deg == 0) q.push(c);
49 }
50
51 std::string result = "";
52 while (!q.empty()) {
53 char u = q.front();
54 q.pop();
55 result += u;
56
57 for (char v : adj[u]) {
58 inDegree[v]--;
59 if (inDegree[v] == 0) {
60 q.push(v);
61 }
62 }
63 }
64
65 // If cycle exists, topological sort length < unique character count
66 return (result.size() == inDegree.size()) ? result : "";
67 }
68};
69
70int main() {
71 Solution sol;
72 std::vector<std::string> words = {"wrt", "wrf", "er", "ett", "rftt"};
73 std::cout << "Kahn Alien Order: " << sol.alienOrder(words) << " (Expected: wertf)\n";
74 std::vector<std::string> invalidWords = {"z", "x", "z"};
75 std::cout << "Cycle Test: \"" << sol.alienOrder(invalidWords) << "\" (Expected: \"\")\n";
76 return 0;
77}

Time & Space Complexity

  • Time complexity: O(C)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Exhaustive Permutation VerificationO(U! * N * L)O(U)Generates all U! permutations and checks if word list is sorted.26! permutations
2.DFS 3-Color Post-Order TraversalO(C)O(1)Recursively visits neighbors, detects back-edges via gray state, reverses post-order.Recursion depth
3.Kahn's Algorithm (BFS In-Degree)OptimalO(C)O(1)Pushes in-degree 0 characters to queue; decrements neighbor in-degrees iteratively.Queue pops

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Failing to handle the prefix violation edge case where a longer word precedes its own prefix.

Pitfall 2:

Only adding characters that participate in directed edges, omitting standalone characters from the final alphabet.

Pitfall 3:

Not checking for duplicate directed edges between the same character pair, which corrupts in-degree counts if sets are not used.

Crucial Edge Cases to Validate:

  • Prefix invalidity (e.g. ['abc', 'ab']) — Detected during adjacent comparison when no differing character is found and w1.length > w2.length -> returns empty string.
  • Directed cycle (e.g. ['z', 'x', 'z']) — Detected when result.length < inDegree.size -> returns empty string.
  • Single word input (e.g. ['z']) — All unique characters initialize with in-degree 0 and enter the queue -> returns z.
  • Disconnected characters (characters with no dependencies) — Start with in-degree 0 and are added to the output order safely.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by stating the graph reduction: 'Each unique character is a vertex; first mismatch between adjacent words gives a directed precedence edge.'
  2. Highlight the critical prefix edge case upfront: 'If w1 has w2 as a prefix and len(w1) > len(w2), it is immediately invalid.'
  3. Explain cycle detection cleanly: 'In Kahn's algorithm, if the final topological string length does not equal the total number of unique characters, a cycle exists, returning empty string.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the input [abc, ab] make the entire dictionary ordering invalid, returning ''?

2.How does Kahn's algorithm identify that a cycle exists in the character precedence graph?

3.Why is it sufficient to ONLY compare adjacent words words[i] and words[i + 1] rather than all pairs words[i] and words[j]?

Back to DSA Sheet