View on NeetCode
View on LeetCode

Problem

There is a new alien language that uses the English 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 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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

Approach: Topological Sort with BFS (Kahn’s Algorithm)

The key insight is to build a directed graph where edge a→b means letter a comes before b, then perform topological sort.

Implementation

from collections import defaultdict, deque

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Initialize in-degree for all characters
        in_degree = {char: 0 for word in words for char in word}
        graph = defaultdict(set)

        # 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: word1 is prefix of word2 but longer
            if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
                return ""

            # Find first differing character
            for j in range(min_len):
                if word1[j] != word2[j]:
                    if word2[j] not in graph[word1[j]]:
                        graph[word1[j]].add(word2[j])
                        in_degree[word2[j]] += 1
                    break

        # Kahn's algorithm for topological sort
        queue = deque([char for char in in_degree if in_degree[char] == 0])
        result = []

        while queue:
            char = queue.popleft()
            result.append(char)

            for next_char in graph[char]:
                in_degree[next_char] -= 1
                if in_degree[next_char] == 0:
                    queue.append(next_char)

        # Check if we processed all characters (no cycle)
        if len(result) != len(in_degree):
            return ""

        return "".join(result)

Approach 2: DFS with Cycle Detection

from collections import defaultdict

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Initialize graph
        graph = {char: set() for word in words for char in word}

        # 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]:
                    graph[word1[j]].add(word2[j])
                    break

        # DFS with cycle detection
        # 0 = unvisited, 1 = visiting, 2 = visited
        visit = {char: 0 for char in graph}
        result = []

        def dfs(char):
            if visit[char] == 1:  # Cycle
                return False
            if visit[char] == 2:  # Already processed
                return True

            visit[char] = 1

            for next_char in graph[char]:
                if not dfs(next_char):
                    return False

            visit[char] = 2
            result.append(char)
            return True

        for char in graph:
            if not dfs(char):
                return ""

        return "".join(reversed(result))

Complexity Analysis

• Time Complexity: O(C), where C is total length of all words. We process each character once and build edges.
• Space Complexity: O(1) or O(26) for the graph, as there are at most 26 letters.

Key Insights

1. Graph Construction: Compare adjacent words to determine order relationships. Only the first differing character pair gives us an edge.

2. Invalid Cases:
   • If word1 is longer but a prefix of word2, the order is invalid
   • If the graph has a cycle, no valid ordering exists

3. Topological Sort: The problem reduces to finding a topological ordering of characters.

4. Partial Ordering: We only learn order relationships from differing characters; same characters give no information.

5. All Characters Matter: Include all characters that appear in words, even if they don’t form edges.

6. DFS Post-Order: DFS naturally produces reverse topological order, so we reverse the result.