Alien Dictionary

For a faster version of Kahn’s algorithm that uses primitive arrays instead of HashMaps, with benchmarks and an explanation of the speedup, see Alien Dictionary, Faster: Primitive Arrays Instead of HashMaps.

Topological sort, in plain language: some tasks have to happen before others. You put on socks before shoes, and you take an intro course before the advanced one. Draw each task as a dot and each “this before that” rule as an arrow. A topological sort lists every task so that all the arrows point forward. If the rules go in a circle, like A before B and B before A, no such list exists. Course schedulers, build tools and spreadsheets all use this idea to decide what to do first. The Alien Dictionary problem below is a topological sort in disguise: the letters are the tasks, and the sorted words tell us which letters come first.

In an alien language uncovered by UC Berkeley archaeologists, words are found to be written with ordinary English letters, but the letters follow an unknown alphabetical order. You are given an array of words, String[] words, that is already sorted according to the alien alphabet. Your job is to recover the order of the letters, if possible.

Each pair of adjacent words gives us one clue. At the first position where the two words differ, the letter in the first word must come before the letter in the second word. We can record each clue as a directed edge in a graph, where every letter is a vertex: if letter a must come before letter b, we draw the edge $\texttt{a} \rightarrow \texttt{b}$.

Example 1. words = ["glor", "glop", "gog", "gr", "lop"]

The edges form a single chain, so the only valid alien alphabet is "glorp".

Example 2. words = ["ab", "ad", "ca", "cb", "d", "e"]

Nothing forces b before c or c before b, so there are two valid alphabets: "abcde" and "acbde".

Example 3. words = ["zap", "zop", "pax", "pox", "oz"]

The edge $\texttt{a} \rightarrow \texttt{o}$ is found twice, and x appears in a word but has no edges at all, so it can go anywhere in the alphabet. One valid alphabet is "azpox"; there are many others.

Two special cases.

• If one word is a prefix of the word before it, such as ["cats", "cat"], the input cannot be sorted in any alphabet, since a real dictionary always lists the shorter word first.
• If the clues contradict each other, such as ["z", "x", "z"] (which gives $\texttt{z} \rightarrow \texttt{x}$ and $\texttt{x} \rightarrow \texttt{z}$), the graph has a cycle, and no valid alphabet exists.

(a) recoverAlienAlphabet

Implement recoverAlienAlphabet, which returns the letters of the alien alphabet in a valid order. If no valid order exists, return the empty string "". If more than one valid order exists, you may return any of them.

public static String recoverAlienAlphabet(String[] words) {
    Map<Character, List<Character>> adj = new HashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();

    // Step 1: Every letter that appears is a vertex, starting at in-degree 0.
    for (String word : words) {
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!adj.containsKey(c)) {
                adj.put(c, new ArrayList<>());
                inDegree.put(c, 0);
            }
        }
    }

    // Step 2: Build edges. The first differing character of adjacent words gives a -> b.
    for (int i = 0; i < words.length - 1; i++) {
        String w1 = words[i];
        String w2 = words[i + 1];
        for (int k = 0; k < w1.length() && k < w2.length(); k++) {
            char a = w1.charAt(k);
            char b = w2.charAt(k);
            if (a != b) {
                adj.get(a).add(b);
                inDegree.put(b, inDegree.get(b) + 1);
                break;
            } else if (k == w2.length() - 1 && w1.length() > w2.length()) {
                return "";  // w2 is a prefix of w1, e.g. ["cats", "cat"]
            }
        }
    }

    // Step 3: Seed the fringe with letters of in-degree 0 (nothing must come before them).
    Queue<Character> fringe = new LinkedList<>();
    for (char c : adj.keySet()) {
        if (inDegree.get(c) == 0) {
            fringe.add(c);
        }
    }

    // Step 4: Remove a letter, append it to the answer, and delete its outgoing edges.
    StringBuilder order = new StringBuilder();
    while (!fringe.isEmpty()) {
        char curr = fringe.remove();
        order.append(curr);
        for (char next : adj.get(curr)) {
            inDegree.put(next, inDegree.get(next) - 1);  // delete edge curr -> next
            if (inDegree.get(next) == 0) {
                fringe.add(next);
            }
        }
    }

    // Step 5: Letters never removed are on a cycle, so no valid order exists.
    if (order.length() != adj.size()) {
        return "";
    }
    return order.toString();
}

Explanation (Kahn’s Algorithm)

Setting up the problem. The words are sorted using an unknown alphabet, and the task is to recover that alphabet’s order. Each piece of evidence says “letter a comes before letter b.” If each letter is a vertex and each such fact is a directed edge $\texttt{a} \rightarrow \texttt{b}$, the question becomes: can we list every vertex so that all edges point forward? That kind of listing is called a topological order. It exists exactly when the graph has no directed cycle, meaning the graph is a DAG.

A key term throughout is in-degree: the number of edges pointing into a vertex. For a letter, it counts how many other letters must come before it.

1. Vertices. Every distinct letter in the input is a vertex. Each one starts at in-degree 0 because no edges have been added yet. Letters that never appear in an edge (like x in Example 3) still belong in the answer, so we add all of them here.

2. Edges and in-degrees. Two neighboring words in the sorted list tell us one thing: at the first position where they differ, the first word’s letter comes before the second word’s letter. For "glor" and "glop", the first difference is at index 3, so $\texttt{r} \rightarrow \texttt{p}$, and p’s in-degree goes up by 1. Characters after the first difference say nothing, because the order was already decided there, so we break.

   There is one special case. If the shorter word runs out while every character so far has matched, then the shorter word is a prefix of the longer one. A real dictionary lists "cat" before "cats", so seeing "cats" first means the input is invalid, and we return "" immediately.

   The same edge can be added more than once, like $\texttt{a} \rightarrow \texttt{o}$ in Example 3. This does not break anything: each copy adds 1 to the in-degree and is subtracted once in Step 4, so the counts stay balanced.

3. Seeding the fringe. A letter with in-degree 0 has no letter that must come before it, so it is safe to place first. We put every such letter into a queue called the fringe, which holds the letters that are ready to be placed. If no letter has in-degree 0, then every letter is waiting on another one, and that can only happen if there is a cycle.

4. Placing letters. Repeatedly remove a letter from the fringe and append it to the answer. Once curr is placed, every letter after it no longer has to wait on curr. So we “delete” each edge $\texttt{curr} \rightarrow \texttt{next}$ by decreasing next’s in-degree by 1. When next reaches 0, everything that had to come before it has been placed, so it joins the fringe.

   We do not need a visited set here. A letter’s in-degree reaches 0 only once, so each letter enters the fringe at most once.

5. Checking for a cycle. Suppose $\texttt{a} \rightarrow \texttt{b}$ and $\texttt{b} \rightarrow \texttt{a}$. Each letter waits for the other, so neither in-degree ever reaches 0, and neither is ever placed. So if the answer has fewer letters than the graph has vertices, some letters are stuck on a cycle. The graph is not a DAG, no valid alphabet exists, and we return "".

Test cases:

Alternative solution: DFS

This solution uses depth-first search (DFS), with a marked set and an onStack set to detect cycles. Steps 1 and 2 build the graph the same way as Kahn’s algorithm, without the in-degree counts.

public static String recoverAlienAlphabet(String[] words) {
    Map<Character, List<Character>> adj = new HashMap<>();

    // Step 1: Every letter that appears is a vertex.
    for (String word : words) {
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!adj.containsKey(c)) {
                adj.put(c, new ArrayList<>());
            }
        }
    }

    // Step 2: Build edges. The first differing character of adjacent words gives a -> b.
    for (int i = 0; i < words.length - 1; i++) {
        String w1 = words[i];
        String w2 = words[i + 1];
        for (int k = 0; k < w1.length() && k < w2.length(); k++) {
            char a = w1.charAt(k);
            char b = w2.charAt(k);
            if (a != b) {
                adj.get(a).add(b);
                break;
            } else if (k == w2.length() - 1 && w1.length() > w2.length()) {
                return "";  // w2 is a prefix of w1, e.g. ["cats", "cat"]
            }
        }
    }

    // Step 3: DFS from every unmarked letter, recording postorder.
    Set<Character> marked = new HashSet<>();
    Set<Character> onStack = new HashSet<>();
    StringBuilder postorder = new StringBuilder();
    for (char c : adj.keySet()) {
        if (!marked.contains(c)) {
            if (dfs(adj, c, marked, onStack, postorder)) {
                return "";  // found a cycle, so no valid order exists
            }
        }
    }

    // Step 4: Reversed postorder is a valid alphabet.
    return postorder.reverse().toString();
}

/** Runs DFS from v. Returns true if it finds a cycle. */
private static boolean dfs(Map<Character, List<Character>> adj, char v,
                           Set<Character> marked, Set<Character> onStack,
                           StringBuilder postorder) {
    marked.add(v);
    onStack.add(v);
    for (char w : adj.get(v)) {
        if (!marked.contains(w)) {
            if (dfs(adj, w, marked, onStack, postorder)) {
                return true;
            }
        } else if (onStack.contains(w)) {
            return true;  // back edge: w is on the current path
        }
    }
    onStack.remove(v);     // v is finished, so it leaves the current path
    postorder.append(v);   // every letter after v has already been recorded
    return false;
}

Step 1: Vertices. Every distinct letter is a vertex, including letters that never appear in an edge. Those letters still belong in the alphabet, so we add all of them up front.

Step 2: Edges. For each pair of adjacent words, the first differing character gives an edge, and we break: characters after the first difference say nothing, because the order was already decided there. If the shorter word runs out while every character so far has matched, the shorter word is a prefix of the longer one, so the input is invalid and we return "" immediately.

The same edge can be added more than once. This is harmless: the second time DFS reaches that neighbor, it is already marked and is simply skipped.

Step 3: DFS with two sets.

• marked holds every letter visited so far. It makes sure each letter is explored only once.
• onStack holds the letters on the current recursion path. A letter is added when DFS enters it and removed when DFS finishes it.

While exploring $v$, suppose DFS finds an edge $v \to w$ where $w$ is still in onStack. Then $w$ is an ancestor of $v$ on the current path, so following the path from $w$ down to $v$ and then the edge $v \to w$ returns to $w$. That is a cycle, and no valid alphabet exists.

marked alone is not enough to detect a cycle. In a diamond, $a \to b$, $a \to c$, $b \to d$, $c \to d$, DFS reaches $d$ a second time through $c$. Letter $d$ is already marked, but there is no cycle: $d$ simply has two paths leading to it. By then $d$ has finished and left onStack, so it is correctly ignored.

We start a DFS from every unmarked letter, because one DFS may not reach every part of the graph.

Step 4: Reversed postorder. A letter is appended to postorder only after the loop over its neighbors finishes, so every letter that must come after it has already been appended. That means postorder lists each letter after everything that must follow it. Reversing it puts each letter before everything that must follow it, which is exactly a valid alphabet.

Results on sample inputs:

The exact output for inputs with several valid orders depends on the order in which letters are explored, so another correct solution may print a different valid alphabet.

Comparison with Kahn’s Algorithm

Kahn’s algorithm solves the same problem by repeatedly removing a letter that no remaining letter must precede. Both approaches build the graph the same way in Steps 1 and 2. The Kahn’s version also tracks each letter’s in-degree, the number of edges pointing into it.

Here $V$ is the number of distinct letters and $E$ is the number of edges. Building the graph also reads every character of the input once.

Both approaches produce a valid alphabet, but they can produce different valid alphabets for the same input.

(b) alienAlphabetIsUnique

Add in two lines into the while loop which allow us to answer the question: Is it true that this Alien Dictionary ordering only has 1 valid ordering? Show the minimal code changes we’d add in order to have our Alien Dictionary algorithm test for this.

Compare Example 1, which has exactly one valid alphabet ("glorp"), with Example 2, which has two ("abcde" and "acbde"). What happens to the fringe in each example?

public static boolean alienAlphabetIsUnique(String[] words) {
    Map<Character, List<Character>> adj = new HashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();

    // Step 1: Every letter that appears is a vertex, starting at in-degree 0.
    for (String word : words) {
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!adj.containsKey(c)) {
                adj.put(c, new ArrayList<>());
                inDegree.put(c, 0);
            }
        }
    }

    // Step 2: Build edges. The first differing character of adjacent words gives a -> b.
    for (int i = 0; i < words.length - 1; i++) {
        String w1 = words[i];
        String w2 = words[i + 1];
        for (int k = 0; k < w1.length() && k < w2.length(); k++) {
            char a = w1.charAt(k);
            char b = w2.charAt(k);
            if (a != b) {
                adj.get(a).add(b);
                inDegree.put(b, inDegree.get(b) + 1);
                break;
            } else if (k == w2.length() - 1 && w1.length() > w2.length()) {
                return false;  // w2 is a prefix of w1, so no valid order exists
            }
        }
    }

    // Step 3: Seed the fringe with letters of in-degree 0 (nothing must come before them).
    Queue<Character> fringe = new LinkedList<>();
    for (char c : adj.keySet()) {
        if (inDegree.get(c) == 0) {
            fringe.add(c);
        }
    }

    // Step 4: Remove a letter, append it to the answer, and delete its outgoing edges.
    StringBuilder order = new StringBuilder();
    while (!fringe.isEmpty()) {
        if (fringe.size() > 1) {
            return false;  // two letters are ready at once, so either could go first
        }
        char curr = fringe.remove();
        order.append(curr);
        for (char next : adj.get(curr)) {
            inDegree.put(next, inDegree.get(next) - 1);  // delete edge curr -> next
            if (inDegree.get(next) == 0) {
                fringe.add(next);
            }
        }
    }

    // Step 5: Letters never removed are on a cycle, so no valid order exists.
    return order.length() == adj.size();
}

Changes from part (a):

• Inside the while loop: the new check if (fringe.size() > 1) { return false; }.
• The method now returns a boolean, so the prefix case returns false, and Step 5 becomes return order.length() == adj.size();.

Explanation

The fringe holds every letter that is ready to be placed: everything that must come before it has already been placed. If the fringe ever holds two letters at once, nothing forces one of them before the other. We could place either one next and still finish with a valid alphabet, so there are at least two valid orders.

In Example 2, after a is removed, both b and c reach in-degree 0 and the fringe holds both. That matches the two valid alphabets, "abcde" and "acbde". In Example 1, the fringe holds exactly one letter at every step (g, then l, then o, then r, then p), so there is never a choice, and "glorp" is the only valid alphabet.

Returning false as soon as the fringe holds two letters is safe even if a cycle exists somewhere else in the graph. A cycle means there are zero valid orders, and two ready letters means there are at least two. Either way, the answer to “is there exactly one valid order?” is false, so we do not need to finish the loop first.

If the fringe never holds more than one letter, the final check still matters: a cycle can leave letters that were never placed, and in that case there is no valid order at all.

(c) alienMustPrecede

Implement alienMustPrecede, which takes in the graph adj built in Steps 1 and 2 of part (a) and two letters x and y. It returns true if x comes before y in every valid alien alphabet, and false otherwise. You may assume the input dictionary is valid, so the graph has no cycles.

Be careful: “my output from part (a) puts x first” is not the same as “x must come first.” Using Example 2:

• a must come before d: every valid alphabet ("abcde" and "acbde") places a first.
• b does not have to come before c: "abcde" places b first, but "acbde" places c first.

public static boolean alienMustPrecede(Map<Character, List<Character>> adj, char x, char y) {
    if (x == y || !adj.containsKey(x) || !adj.containsKey(y)) {
        return false;
    }
    Queue<Character> fringe = new LinkedList<>();
    Set<Character> traversed = new HashSet<>();
    fringe.add(x);
    traversed.add(x);
    while (!fringe.isEmpty()) {
        char curr = fringe.remove();
        for (char next : adj.get(curr)) {
            if (next == y) {
                return true;  // found a path x -> ... -> curr -> y
            }
            if (!traversed.contains(next)) {
                traversed.add(next);
                fringe.add(next);
            }
        }
    }
    return false;
}

Explanation

Each edge is a forced “comes before.” If there is a path $\texttt{x} \rightarrow \cdots \rightarrow \texttt{y}$, then x comes before the next letter on the path, which comes before the next, and so on until y, so every valid alphabet places x before y. If there is no path, nothing forces x first, and some valid alphabet places y before x. So the question becomes: is y reachable from x?

We answer it with a traversal from x. As soon as y appears as a neighbor, a path exists, so we return true immediately. If the fringe empties without finding y, no path exists, and we return false.

Why the visited set matters

How does a Set<Character> visited help us with efficiency in terms of traversing the graph, more specifically, our directed graph without cycles?

Once a letter has been added to the fringe, its neighbors are guaranteed to be explored when it is removed. Adding the same letter again would repeat that work without finding anything new, so traversed records every letter that has already been added, and we skip it the next time.

A letter can be reached by more than one path. In Example 2, d is reached through both b and c. Without the set, d would be added to the fringe once per path, and so would everything after it. Suppose y were a letter not reachable from a, so the loop runs until the fringe is empty. Without the set, starting from a:

Both d and e are processed twice. Each diamond like this doubles the number of paths to every letter below it, so a chain of $k$ diamonds makes the last letter enter the fringe $2^k$ times: the work grows exponentially in the size of the graph. With the set, each letter is added to the fringe at most once, and its neighbors are looped over at most once, so the traversal runs in $\Theta(V + E)$ time, where $V$ is the number of letters and $E$ is the number of edges.

Because the graph has no cycles, the traversal still finishes without the set, and it still returns the correct answer. The set is about efficiency here, not about stopping conditions. (In a graph with cycles, the set would also be needed to stop: without it, a cycle like $\texttt{a} \rightarrow \texttt{b} \rightarrow \texttt{a}$ would keep adding letters to the fringe forever.)