Alien Dictionary

Problem Description

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

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 language.

Return a string of the unique letters in the alien language sorted in lexicographically increasing order. If no valid ordering exists, return "". If there are multiple solutions, return any of them.

Examples

Constraints

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

Extracting Character Ordering Dependencies as a Directed Graph

The words are sorted lexicographically. This means comparing adjacent words tells us the order of characters. If we compare "wrt" and "wrf", the first mismatch is at the third character: 't' must come before 'f'.

We can represent these character pairs as directed edges in a graph: t -> f. Finding the sorted alphabet order is equivalent to finding a topological sort of this directed graph. If the graph contains a cycle (like a -> b and b -> a), no valid ordering exists, and we return "". We must also check for invalid prefixes: if "apple" comes before "app", this is invalid because a shorter prefix must always come first.

Solution 1: Topological Sort (DFS / Post-Order)

Build an adjacency list from the mismatching characters of adjacent words. Run a depth-first search to detect cycles and build the topological ordering in reverse post-order.

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        // initialize adjacency list and visited map
        Map<Character, List<Character>> adj = new HashMap<>();
        Map<Character, Integer> visited = new HashMap<>(); // 0=unvisited, 1=visiting, 2=visited
        
        for (String w : words) {
            for (char c : w.toCharArray()) {
                adj.putIfAbsent(c, new ArrayList<>());
                visited.put(c, 0);
            }
        }

        // build graph edges
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i];
            String w2 = words[i + 1];
            
            // check invalid prefix case: "apple" before "app" is invalid
            if (w1.length() > w2.length() && w1.startsWith(w2)) {
                return "";
            }
            
            int minLen = Math.min(w1.length(), w2.length());
            for (int j = 0; j < minLen; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    adj.get(c1).add(c2);
                    break; // only the first mismatch dictates the order
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char c : adj.keySet()) {
            if (visited.get(c) == 0) {
                if (hasCycle(c, adj, visited, sb)) {
                    return "";
                }
            }
        }
        return sb.reverse().toString();
    }

    private boolean hasCycle(char c, Map<Character, List<Character>> adj, Map<Character, Integer> visited, StringBuilder sb) {
        visited.put(c, 1); // mark as visiting
        for (char neighbor : adj.get(c)) {
            if (visited.get(neighbor) == 1) return true; // cycle detected
            if (visited.get(neighbor) == 0) {
                if (hasCycle(neighbor, adj, visited, sb)) return true;
            }
        }
        visited.put(c, 2); // mark as visited
        sb.append(c);
        return false;
    }
}

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        # initialize graph
        adj = {c: set() for w in words for c in w}

        # build graph edges
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            # check invalid prefix case
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""

            min_len = min(len(w1), len(w2))
            for j in range(min_len):
                if w1[j] != w2[j]:
                    adj[w1[j]].add(w2[j])
                    break  # only the first mismatch dictates the order

        visited = {}  # False = visiting, True = visited
        result = []

        def dfs(c):
            if c in visited:
                return visited[c]  # returns True if already visited, False if cycle

            visited[c] = False  # mark as visiting
            for neighbor in adj[c]:
                if not dfs(neighbor):
                    return False

            visited[c] = True  # mark as visited
            result.append(c)
            return True

        for c in adj:
            if not dfs(c):
                return ""

        return "".join(reversed(result))

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

class Solution {
private:
    bool dfs(char c, std::unordered_map<char, std::unordered_set<char>>& adj, 
             std::unordered_map<char, int>& visited, std::string& result) {
        visited[c] = 1; // mark as visiting
        for (char neighbor : adj[c]) {
            if (visited[neighbor] == 1) return true; // cycle detected
            if (visited[neighbor] == 0) {
                if (dfs(neighbor, adj, visited, result)) return true;
            }
        }
        visited[c] = 2; // mark as visited
        result += c;
        return false;
    }

public:
    std::string alienOrder(std::vector<std::string>& words) {
        std::unordered_map<char, std::unordered_set<char>> adj;
        std::unordered_map<char, int> visited;

        for (const std::string& w : words) {
            for (char c : w) {
                adj[c] = std::unordered_set<char>();
                visited[c] = 0;
            }
        }

        // build graph edges
        for (size_t i = 0; i < words.size() - 1; i++) {
            std::string w1 = words[i];
            std::string w2 = words[i + 1];

            // check invalid prefix case
            if (w1.length() > w2.length() && w1.compare(0, w2.length(), w2) == 0) {
                return "";
            }

            size_t minLen = std::min(w1.length(), w2.length());
            for (size_t j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    adj[w1[j]].insert(w2[j]);
                    break; // only the first mismatch dictates the order
                }
            }
        }

        std::string result = "";
        for (auto& pair : adj) {
            char c = pair.first;
            if (visited[c] == 0) {
                if (dfs(c, adj, visited, result)) return "";
            }
        }

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

Complexity Analysis:

• Time Complexity: O(C) where C is the total length of all words in the input. Finding the first mismatch takes at most the length of the words, and the DFS traversal visits each character and edge at most once.
• Space Complexity: O(V + E) = O(1) auxiliary space, as the vertices (V) are limited to the 26 English letters, making graph storage constant.

Where it breaks: If there are multiple disconnected components in the graph, the topological sort still yields a valid ordering, but it will not be unique. This is acceptable as the problem permits any valid ordering.

Common Mistakes

• Forgetting the invalid prefix edge case. If "words = ["abc", "ab"]", "abc" is longer but has "ab" as a prefix. Since "abc" comes first, this violates lexicographical rules. You must detect this and return "".
• Adding edges for multiple character mismatches. For words "ab" and "cd", only compare the first character mismatch ('a' and 'c'). The relationship between 'b' and 'd' is unknown because the sorting is already decided by the first character.
• Not detecting cycles. In topological sorting, cycle detection is mandatory. Unhandled cycles like a -> b -> a will result in incorrect sorting output.

Frequently Asked Questions

Can there be characters in the language that do not appear in any word? No. We only concern ourselves with the unique characters present in the given word dictionary.

What does it mean if the output can have multiple solutions? If there are character orders that do not have dependencies between them, any order is acceptable. For example, if both a -> b and c -> d exist, but no relation between a and c is defined, acbd and cabd are both valid solutions.

What does this problem test in interviews? It tests your ability to model relationships as a directed graph, construct graph adjacency lists from text, and execute topological sorting with cycle detection.

← All Problems