Alien Dictionary

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.

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.

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.

Approach: Topological Sort (Kahn’s Algorithm)

Algorithm

1. Initialize a graph and an indegree map containing every letter that appears in the words
2. Compare each pair of adjacent words; the first differing character gives a directed edge c1 -> c2 (c1 comes before c2). If the second word is a prefix of the first and shorter, the order is invalid
3. Run BFS-based topological sort: repeatedly take letters with indegree 0
4. If the output length is less than the number of unique letters, there is a cycle -> return ""

Time & Space Complexity

• Time Complexity: O(C) - C is the total number of characters across all words
• Space Complexity: O(1) - at most 26 letters, so the graph is constant size

Java Implementation

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class AlienDictionary {

    /**
     * Derive the order of letters in the alien language.
     * @param words Sorted words from the alien dictionary
     * @return A valid letter order, or "" if invalid
     */
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();

        for (String word : words) {
            for (char c : word.toCharArray()) {
                graph.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 len = Math.min(w1.length(), w2.length());

            boolean found = false;
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (graph.get(c1).add(c2)) {
                        indegree.put(c2, indegree.get(c2) + 1);
                    }
                    found = true;
                    break;
                }
            }

            if (!found && w1.length() > w2.length()) {
                return "";
            }
        }

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

        StringBuilder result = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            result.append(c);
            for (char next : graph.get(c)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }

        return result.length() == indegree.size() ? result.toString() : "";
    }

    // Test method
    public static void main(String[] args) {
        AlienDictionary ad = new AlienDictionary();
        System.out.println("Input: words = [\"wrt\",\"wrf\",\"er\",\"ett\",\"rftt\"]");
        System.out.println("Output: \"" + ad.alienOrder(new String[]{"wrt", "wrf", "er", "ett", "rftt"}) + "\""); // Expected: "wertf"

        System.out.println("Input: words = [\"z\",\"x\"]");
        System.out.println("Output: \"" + ad.alienOrder(new String[]{"z", "x"}) + "\""); // Expected: "zx"

        System.out.println("Input: words = [\"z\",\"x\",\"z\"]");
        System.out.println("Output: \"" + ad.alienOrder(new String[]{"z", "x", "z"}) + "\""); // Expected: ""
    }
}

Example Walkthrough

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

1. Compare “wrt” and “wrf”: differ at index 2 (‘t’ vs ‘f’) -> edge t -> f
2. Compare “wrf” and “er”: differ at index 0 (‘w’ vs ‘e’) -> edge w -> e
3. Compare “er” and “ett”: differ at index 1 (‘r’ vs ‘t’) -> edge r -> t
4. Compare “ett” and “rftt”: differ at index 0 (‘e’ vs ‘r’) -> edge e -> r

Graph: w->e->r->t->f. Kahn’s algorithm yields “wertf”.

For words = ["z","x","z"]: edge z -> x from pair 1, and from “x” vs “z” edge x -> z, forming a cycle -> return "".

Key Points

1. First Difference Only: Only the first differing character between adjacent words yields an ordering constraint
2. Invalid Prefix: If a word is a prefix of the previous word but longer, the input is inconsistent
3. Cycle Detection: A topological sort that processes fewer nodes than exist implies a cycle
4. All Letters Tracked: Every appearing letter starts with indegree 0 in the map, even without edges
5. Duplicate Edge Guard: A Set per node prevents double-counting indegree for repeated constraints