97.Alien Dictionary

HardBlind 75Graphs · 18/19

Problem

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

Return a string containing every unique letter that appears in words, ordered according to the alien alphabet. If the ordering is contradictory (no valid order exists), return "". If several orders are valid, any of them is accepted.

Examples

Input:  words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Explanation: wrt<wrf gives t<f, wrf<er gives w<e, er<ett gives r<t, ett<rftt gives e<r.
             Chain: w < e < r < t < f.

Input:  words = ["z","x","z"]
Output: ""
Explanation: z<x and x<z contradict each other (a cycle).

Input:  words = ["abc","ab"]
Output: ""
Explanation: A longer word can never come before its own prefix, so the input is invalid.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

💡 Key Insight

Comparing adjacent words gives all the information we can extract: the first position where they differ tells us c1 comes before c2; nothing after that position matters. These facts form a directed graph over letters, and a valid alphabet is exactly a topological order of that graph. A cycle means a contradiction (return ""), and so does a word followed by its own proper prefix.

DFS Topological Sort

TimeO(C)SpaceO(U + E)

Intuition

Build the letter graph, then run DFS with three states per letter: unvisited, visiting (on the current path), and done. Reaching a "visiting" letter means a cycle. When a letter finishes, append it — post-order gives the reverse topological order, so reverse at the end.

Algorithm

Add every letter in words as a node.
For each adjacent pair (w1, w2): find the first differing index j; add edge w1[j] -> w2[j]. If no difference and w1.length() > w2.length(), return "".
DFS from every unvisited letter; return "" on a cycle; append each letter after its neighbours finish.
Reverse the built string.

Visualization

graph: t->f, w->e, r->t, e->r

dfs(w) -> dfs(e) -> dfs(r) -> dfs(t) -> dfs(f)
post-order: f, t, r, e, w
reversed:   w, e, r, t, f  -> "wertf"

Code

java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    private final Map<Character, Set<Character>> adj = new HashMap<>();
    private final Map<Character, Integer> state = new HashMap<>(); // 1 = visiting, 2 = done
    private final StringBuilder order = new StringBuilder();

    public String alienOrder(String[] words) {
        for (String w : words) {
            for (char c : w.toCharArray()) {
                adj.putIfAbsent(c, new HashSet<>());
            }
        }
        for (int i = 0; i + 1 < words.length; i++) {
            String w1 = words[i], w2 = words[i + 1];
            int len = Math.min(w1.length(), w2.length());
            if (w1.length() > w2.length() && w1.startsWith(w2)) {
                return ""; // longer word before its own prefix
            }
            for (int j = 0; j < len; j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    adj.get(w1.charAt(j)).add(w2.charAt(j));
                    break; // only the first difference matters
                }
            }
        }
        for (char c : adj.keySet()) {
            if (!dfs(c)) {
                return "";
            }
        }
        return order.reverse().toString();
    }

    // returns false if a cycle is found
    private boolean dfs(char c) {
        Integer s = state.get(c);
        if (s != null) {
            return s == 2; // 1 means we are still on the path: cycle
        }
        state.put(c, 1);
        for (char next : adj.get(c)) {
            if (!dfs(next)) {
                return false;
            }
        }
        state.put(c, 2);
        order.append(c); // post-order
        return true;
    }
}

Complexity

Time: O(C) — C is the total number of characters across all words (building edges), plus O(U + E) for the DFS where U <= 26.
Space: O(U + E) — at most 26 nodes and 26² edges.

Kahn's Algorithm — BFS Topological SortOptimal

TimeO(C)SpaceO(U + E)

Intuition

Count each letter's in-degree (how many letters must come before it). Letters with in-degree 0 can go first. Output one, decrement the in-degree of its successors, and enqueue any that drop to 0. If we cannot output all letters, the remaining ones sit on a cycle. This is iterative (no recursion) and makes cycle detection a simple length check.

Algorithm

Add every letter as a node with in-degree 0.
For each adjacent word pair, apply the prefix check and add the first-difference edge c1 -> c2 (incrementing indeg[c2] only if the edge is new).
Queue every letter with in-degree 0.
Pop, append to the result, decrement neighbours' in-degree, enqueue those that reach 0.
If the result length is less than the number of letters, return "".

Dry Run

flowchart LR
    W["w<br/>indeg 0"] -->|"wrf < er"| E["e<br/>indeg 1"]
    E -->|"ett < rftt"| R["r<br/>indeg 1"]
    R -->|"er < ett"| T["t<br/>indeg 1"]
    T -->|"wrt < wrf"| F["f<br/>indeg 1"]

queue=[w]        pop w -> e indeg 0     result="w"
queue=[e]        pop e -> r indeg 0     result="we"
queue=[r]        pop r -> t indeg 0     result="wer"
queue=[t]        pop t -> f indeg 0     result="wert"
queue=[f]        pop f                  result="wertf"
5 letters output == 5 letters total -> "wertf"

Code

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indeg = new HashMap<>();
        for (String w : words) {
            for (char c : w.toCharArray()) {
                adj.putIfAbsent(c, new HashSet<>());
                indeg.putIfAbsent(c, 0);
            }
        }

        for (int i = 0; i + 1 < words.length; i++) {
            String w1 = words[i], w2 = words[i + 1];
            if (w1.length() > w2.length() && w1.startsWith(w2)) {
                return ""; // invalid: prefix after the longer word
            }
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j), c2 = w2.charAt(j);
                if (c1 != c2) {
                    if (adj.get(c1).add(c2)) { // count each edge only once
                        indeg.merge(c2, 1, Integer::sum);
                    }
                    break;
                }
            }
        }

        Deque<Character> queue = new ArrayDeque<>();
        for (Map.Entry<Character, Integer> e : indeg.entrySet()) {
            if (e.getValue() == 0) {
                queue.offer(e.getKey());
            }
        }
        StringBuilder result = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            result.append(c);
            for (char next : adj.get(c)) {
                if (indeg.merge(next, -1, Integer::sum) == 0) {
                    queue.offer(next);
                }
            }
        }
        // letters left over are part of a cycle
        return result.length() == indeg.size() ? result.toString() : "";
    }
}

Complexity

Time: O(C) — scanning all characters dominates; the BFS is O(U + E) with U <= 26, E <= 26².
Space: O(U + E) — the graph and in-degree map, bounded by the alphabet size.

Complexity Comparison

Approach	Time	Space
DFS Topological Sort	O(C)	O(U + E)
Kahn's Algorithm	O(C)	O(U + E)

Common Pitfalls

Comparing every character of two adjacent words — only the first difference creates an edge.
Missing the prefix case ["abc","ab"], which must return "".
Forgetting letters that never appear in any edge (e.g. a single word ["z"] should return "z").
Incrementing in-degree twice for a duplicate edge, which leaves a letter stuck with in-degree 1.
Comparing non-adjacent words — unnecessary, since order is transitive.