Alien Dictionary

The problem

An alien language uses lowercase English letters, but in an unknown order. You are given a list of words that is sorted by the rules of that language, the way a dictionary is sorted.

Return a string with every letter that appears in the words, in an order that fits the sorted list. If several orders fit, return any of them. If no order fits, return "".

Example 1

Input: words = ["dab", "dac", "bc", "bad", "ca"]

Output: "dbca"

“dab” before “dac” means b comes before c. “dac” before “bc” means d before b. “bc” before “bad” means c before a. Together: d, b, c, a.

word 1

dab

word 2

dac

word 3

bc

word 4

bad

word 5

ca

Example 2

Input: words = ["x", "y", "x"]

Output: ""

The list says x comes before y, and also that y comes before x. Both cannot be true.

Example 3

Input: words = ["abc", "ab"]

Output: ""

A word always comes after its own prefix, so “abc” cannot be listed before “ab”.

Constraints

• 1 ≤ words.length ≤ 100 (call it N)
• 1 ≤ words[i].length ≤ 100
• Only lowercase English letters. Call the total number of letters in all words C.

Clarifying questions

If many orders fit, which one do we return?

Any of them. A letter that no rule mentions can go anywhere.

What if a word comes before its own prefix?

That list cannot be sorted in any alphabet, so return "".

Must the answer hold only the letters that appear?

Yes. Every letter in the words, each once, and no others.

What does one pair of words tell us?

Only their first different letter matters. Everything after it says nothing.

Spot the pattern

Each pair of neighboring words gives a rule “x comes before y”: a directed edge from letter x to letter y. Finding an order of the letters that follows every edge is a topological sort, the same graph search as in Course Schedule. A loop in the rules, like Example 2, means no order exists.

Solutions

Rules, then topological sortO(C)

Show all

There is only one approach worth showing. Trying every order of the letters would take up to 26! tries, and comparing every pair of words, not just neighbors, gives no new rules: sorted order already follows from the neighbors.

Rules, then topological sort O(C)

The idea

There are two parts.

1. Learn the rules. For each pair of neighboring words, walk them together until the first position where they differ. If the letters there are x in the first word and y in the second, then x comes before y. Add that edge once. If one word runs out first with no difference, the shorter one must be first. If the longer word comes first, the list is impossible: return "".
2. Order the letters. For each letter, count how many rules point at it. Put the letters with a count of 0 in a queue. Take letters from the front. Each taken letter lowers the count of every letter it points at, and a count that hits 0 joins the queue. If every letter gets taken, that is the answer. If some never reach 0, the rules have a loop: return "".

Why it is correct: a dictionary is sorted by the first letter that differs, so each pair gives exactly one true rule, and nothing else is known about the order. The topological sort then lists a letter only after every letter that must come before it.

Walkthrough

1. after = {}; missing = {} for every letter in the words
2. for each pair of neighboring words first_word, second_word:
3. find the first position where first_word and second_word differ
4. if found and first_letter → second_letter is new: add it, missing[second_letter] += 1
5. ready = letters with missing == 0
6. while ready:
7. letter = ready.pop_front(); order += letter
8. for next_letter in after[letter]: missing[next_letter] -= 1, and queue it at 0
9. return order if it has every letter, else ""

The words are sorted in the alien alphabet. Neighboring words tell us about the order. The letters used are d, a, b, c. No rules are known yet.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Rules, then topological sort: each pair of neighboring words gives at most
    // one rule "x comes before y". Kahn's algorithm orders the letters in O(C) total.
    public String alienOrder(String[] words) {
        // Keep the letters in first-seen order, and store each rule only once.
        Map<Character, Set<Character>> after = new LinkedHashMap<>();
        for (String word : words)
            for (char letter : word.toCharArray()) after.putIfAbsent(letter, new LinkedHashSet<>());
        Map<Character, Integer> missing = new HashMap<>();
        for (char letter : after.keySet()) missing.put(letter, 0);
        for (int i = 0; i + 1 < words.length; i++) {
            String firstWord = words[i], secondWord = words[i + 1];
            int j = 0;
            while (j < firstWord.length() && j < secondWord.length()
                && firstWord.charAt(j) == secondWord.charAt(j))
                j++;
            if (j < firstWord.length() && j < secondWord.length()) {
                // Only the first difference says anything about the order.
                if (after.get(firstWord.charAt(j)).add(secondWord.charAt(j)))
                    missing.merge(secondWord.charAt(j), 1, Integer::sum);
            } else if (firstWord.length() > secondWord.length()) {
                // No difference: a longer word before its own prefix breaks the order.
                return "";
            }
        }
        Deque<Character> ready = new ArrayDeque<>();
        for (char letter : after.keySet()) if (missing.get(letter) == 0) ready.add(letter);
        StringBuilder order = new StringBuilder();
        while (!ready.isEmpty()) {
            char letter = ready.poll();
            order.append(letter);
            for (char nextLetter : after.get(letter)) {
                missing.merge(nextLetter, -1, Integer::sum);
                if (missing.get(nextLetter) == 0) ready.add(nextLetter);
            }
        }
        // Letters on a cycle never reach 0, so the order is impossible.
        return order.length() == after.size() ? order.toString() : "";
    }
}

Big O

Time O(C)Space O(U + R)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are four loops. Collecting the letters reads each of the C letters once. For each pair of words, a loop compares letters until the first difference. The while loop pops one letter per run, and the inner for follows each rule out of it. Each of these is a fixed job, so 1 step.

   1. after = {}; missing = {} for every letter in the words
   2. for each pair of neighboring words first_word, second_word:
   3. find the first position where first_word and second_word differ
   4. if found and first_letter → second_letter is new: add it, missing[second_letter] += 1
   5. ready = letters with missing == 0
   6. while ready:
   7. letter = ready.pop_front(); order += letter
   8. for next_letter in after[letter]: missing[next_letter] -= 1, and queue it at 0
   9. return order if it has every letter, else ""

2. 2 Count the runs on Example 1

   The table has one column per pair of neighboring words. “dab” and “dac” need 3 comparisons to find their difference, at the last letter. The other pairs differ sooner.

   13 letters read + 7 compared + 4 pops + 3 rules followed = 27 steps.

   	dab / dac	dac / bc	bc / bad	bad / ca
   letters compared	3	1	2	1

   all steps

   13 read + 7 compared + 4 pops + 3 rules = 27

3. 3 Write the count for any n

   A pair compares at most as many letters as the first word has, so all the comparisons add up to at most C. Call the number of different letters U and the number of rules R. Each letter appears in the words, so U ≤ C. Each pair adds at most one rule, so R ≤ N − 1 < C.

   C (read) + C (compare) + U (pops) + R (rules) ≤ 4 × C steps

   Check it with Example 1: 4 × 13 = 52 at most. The real run used 27.

4. 4 Keep only the part that grows fastest

   Drop the 4. What is left is C, the size of the input. Every letter has to be read at least once, so no method can do better.

   So the time is O(C).

5. S Space: count the extra memory the same way

   The rules take one entry per letter and one per rule: U + R. The counts and the queue hold U each. With only 26 letters, U is at most 26 and R at most 26 × 25, so in practice this is a small fixed amount. The space is O(U + R).

   after: U letters, R rulesmissing counts (U)ready queue (up to U)

Common mistake

Reading rules past the first difference

In “dab” and “dac”, only b and c are compared. It is tempting to also pair up the letters after the first difference, or to compare words that are not neighbors, letter by letter. Those give false rules, and a correct list can then look impossible.

Tested at the limits

2,000 random word lists of up to 6 words over up to 5 letters. Half are sorted by a hidden order, and the rest are often contradictory, sometimes with a word right before its own prefix. Any order that fits the words is right, so each order returned was checked to be valid, and an empty answer came back exactly when a check that tries every order of the letters found none.

Largest inputs	Result
100 words of 100 letters (the most allowed), sorted by a hidden order of all 26 letters. Neighbors share their first 90 letters, so finding each first difference reads most of the 10,000 letters. Rules, then topological sort.	Under 0.01 s, and under 0.01 MB of extra memory: at most 26 letters and 99 rules, O(U + R).
The same words with two of them swapped, so the rules contradict. Rules, then topological sort.	Under 0.01 s, and an empty answer, as it should be.