☕ DSA Java Articles

Topics › Graphs › Topo Sort and Problems

Alien Dictionary

Hard TUF ID 503 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

An alien language uses the first k letters of the English alphabet, but in an unknown order. You are given a list of N words that is sorted according to that alien order (sorted the way a dictionary is: compare letter by letter, and a word comes before any longer word it is a prefix of). Return a string containing each of the k letters exactly once, in an order consistent with the list. If several orders are consistent, return any of them. If no order can make the list sorted, return "".

Constraints: 1 ≤ N ≤ 300, 1 ≤ k ≤ 26, 1 ≤ word length ≤ 50, words use only the first k letters.

Example 1

words = ["baa", "abcd", "abca", "cab", "cad"], k = 4
answer = "bdac"

Example 2

words = ["caa", "aaa", "aab"], k = 3
answer = "cab"           // c before a ("caa" < "aaa"), a before b ("aaa" < "aab")

The LeetCode version (premium) differs slightly: the alphabet is “every letter that appears in the words” rather than the first k letters. The same algorithm works if you track which letters are present and only emit those.

What a sorted list tells us. Compare two adjacent words. Scan until the first position where they differ. If the letters there are x in the upper word and y in the lower one, then x comes before y in the alien alphabet. Two other things are worth stating:

Only adjacent pairs are needed: sortedness is transitive, so any constraint implied by two words further apart is already implied by the chain of adjacent pairs between them.

Approach 1: Brute force, try every alphabet

Intuition. The answer is one of the k! orderings of the letters. Generate them one by one and, for each, check whether the word list is sorted under that ranking. The first ordering that passes is a valid answer. It is hopeless for large k, but it is a correct reference and shows exactly what “consistent with the list” means.

Algorithm.

  1. Start with the letters a, b, c, ... in an array.
  2. Generate permutations by swapping each remaining letter into the current position and recursing.
  3. At a full permutation, compute each letter’s rank and check every adjacent word pair using the rules above.
  4. Return the first permutation that passes, or "" if none does.
static String bruteForce(String[] words, int k) {
    char[] letters = new char[k];
    for (int i = 0; i < k; i++) letters[i] = (char) ('a' + i);
    String found = tryAll(letters, 0, words);
    return found == null ? "" : found;
}

/** Swap-based permutation: fixes letters[0..pos-1] and tries every remaining letter at position pos. */
static String tryAll(char[] letters, int pos, String[] words) {
    if (pos == letters.length) return isSortedUnder(words, letters) ? new String(letters) : null;
    for (int i = pos; i < letters.length; i++) {
        swap(letters, pos, i);
        String found = tryAll(letters, pos + 1, words);
        swap(letters, pos, i);
        if (found != null) return found;
    }
    return null;
}

static void swap(char[] a, int i, int j) {
    char t = a[i];
    a[i] = a[j];
    a[j] = t;
}

/** True if every adjacent pair of words is in non-decreasing order when letters rank as in order. */
static boolean isSortedUnder(String[] words, char[] order) {
    int[] rank = new int[26];
    for (int i = 0; i < order.length; i++) rank[order[i] - 'a'] = i;
    for (int w = 0; w + 1 < words.length; w++) {
        String a = words[w], b = words[w + 1];
        int len = Math.min(a.length(), b.length()), i = 0;
        while (i < len && a.charAt(i) == b.charAt(i)) i++;
        if (i == len) {
            if (a.length() > b.length()) return false;    // a longer word may not precede its own prefix
        } else if (rank[a.charAt(i) - 'a'] > rank[b.charAt(i) - 'a']) {
            return false;
        }
    }
    return true;
}

Complexity. Time O(k! × N × L) where L is the word length: k! candidate alphabets, each checked against all adjacent pairs. For k = 26 that is about 4 × 10^26 candidates, so this only runs for tiny k. Space O(k) for the recursion and the rank table.

Approach 2: Optimal, build a graph and topologically sort it

Intuition. Each adjacent pair gives at most one fact of the form “x before y”. Make each letter a node and each fact an edge x → y. An alphabet consistent with the list is exactly an ordering of the letters in which every edge points forward: a topological order. Kahn’s algorithm finds one, or tells us none exists because the facts contain a cycle (a before b and b before a).

Letters that never appear in any fact have in-degree 0 and are emitted along with the rest; they may go anywhere, and Kahn’s simply places them early.

Algorithm.

  1. For each adjacent pair, find the first differing position i.
    • No difference and the upper word is longer: return "".
    • No difference otherwise: skip, the pair gives no information.
    • Else add the edge upper[i] → lower[i] and increase the in-degree of lower[i].
  2. Queue every letter with in-degree 0.
  3. Pop a letter, append it, decrement its successors, queue any that reach 0.
  4. If all k letters were appended, return the string; otherwise a cycle exists, so return "".
static String optimal(String[] words, int k) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < k; i++) adj.add(new ArrayList<>());
    int[] indegree = new int[k];
    for (int w = 0; w + 1 < words.length; w++) {
        String a = words[w], b = words[w + 1];
        int len = Math.min(a.length(), b.length()), i = 0;
        while (i < len && a.charAt(i) == b.charAt(i)) i++;
        if (i == len) {
            if (a.length() > b.length()) return "";       // "abc" before "ab": no order can explain it
            continue;                                     // a is a prefix of b: no information
        }
        int u = a.charAt(i) - 'a', v = b.charAt(i) - 'a';
        adj.get(u).add(v);                                // letter u comes before letter v
        indegree[v]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int c = 0; c < k; c++) if (indegree[c] == 0) queue.add(c);
    StringBuilder order = new StringBuilder();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.append((char) ('a' + u));
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) queue.add(v);
        }
    }
    return order.length() == k ? order.toString() : "";   // letters left over sit on a cycle
}

Dry run on Example 1. The adjacent pairs give:

pair first difference edge
baa / abcd b vs a b → a
abcd / abca d vs a d → a
abca / cab a vs c a → c
cab / cad b vs d b → d

In-degrees are a: 2, b: 0, c: 1, d: 1. Kahn’s algorithm then runs:

pop output in-degree changes queue after
start     [b]
b b a: 2 → 1, d: 1 → 0 [d]
d bd a: 1 → 0 [a]
a bda c: 1 → 0 [c]
c bdac none []

All four letters were output, so the answer is "bdac". Here the order is forced; in general several answers may be valid.

Complexity. Time O(N × L + k): comparing adjacent pairs reads each character at most twice, there are at most N - 1 edges, and Kahn’s algorithm is linear in letters plus edges. Space O(k + N) for the adjacency list, the in-degree array and the queue.

Edge cases and pitfalls