What is the brute force approach and complexity for Alien Dictionary?

Try each order of the letters; keep the first one that sorts the list with time complexity O(U! · N · L) and space complexity O(U).

What is the optimal approach and complexity for Alien Dictionary?

One rule per neighbouring pair; then place letters that have nothing before them with optimal time complexity O(N · L) and space complexity O(1).

How do you identify the pattern for Alien Dictionary?

Look for key signals in the prompt: "words sorted in an alien language" indicates The sorted list hides a set of letter comparisons. Build the graph from them, then sort it.; "return any valid order" indicates This is a topological sort: any order that puts every arrow's tail before its head.; "empty string if no order" indicates A cycle makes Kahn stop early, so the count of placed letters tells us..

Alien Dictionary

Hard·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelTopological Sort — Build the graph, then sort (Kahn's algorithm)

Complexity:O(U! · N · L)→O(N · L)

Key Insight

Compare each pair of neighbours and stop at its first differing letter. That one letter gives an arrow. Then run Kahn's algorithm on the arrows: place letters with no arrows pointing in, and remove their arrows as you go.

Core Validity Invariant

A letter can be placed next only when every arrow pointing into it has already been placed. Then no rule is broken, because nothing unplaced must come before it.

Problem

You get a list of words. The list is sorted by the dictionary order of an alien language. The alien alphabet uses lowercase letters, but you do not know how those letters are ordered.

Find a letter order that makes the list sorted. Return every letter that appears in the words, once each, in that order, as one string.

More than one order can work. Any valid one is accepted. If no order can make the list sorted, return an empty string.

Input

words: a list of strings, given in the alien dictionary order.

Output

One string with each letter that appears in words exactly once, in a valid alien order. Or an empty string if no order works.

Example 1

Input: words = ["baa", "abcd", "abca", "cab", "cad"]

Output: "bdac"

The neighbouring pairs say: b before a (baa vs abcd), d before a (abcd vs abca), a before c (abca vs cab), b before d (cab vs cad). "bdac" respects all four. Any other valid order is also accepted.

Example 2

Input: words = ["caa", "aaa", "aab"]

Output: "cab"

caa vs aaa says c comes before a. aaa vs aab says a comes before b. Only one order fits: c, a, b.

Example 3

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

Output: ""

ab before ba says a comes before b. ba before ab says b comes before a. Those two rules clash, so no order works.

Constraints

• Every word uses only lowercase letters a to z.
• Some inputs have no valid order. For those, return an empty string.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Each pair of neighbouring words tells me something about two letters. Which letters in the pair actually matter?
2.
For the words cat and cap, do the letters after the first difference tell me anything? Why or why not?
3.
If I draw every "x comes before y" fact as an arrow x → y, what kind of graph do I get, and what do I need to find in it?
4.
Which letters can go first in the answer?
5.
If a set of arrows forms a loop, what happens to the letters in that loop while I keep placing letters that have no arrows pointing in?

Brute force approach

Idea

The answer uses each letter that appears exactly once, so it is one order of those letters. Try every order. For each one, check that every word is at most the word after it, comparing letters by their place in that order. The first order that passes is the answer.

Thinking process

1
The answer is a permutation of the letters that appear. Trying every permutation is simple, though the count grows fast with the number of letters.
2
For one candidate, give each letter its rank: its position in the candidate string.
3
Check each neighbouring pair with those ranks. Under the candidate abc, the pair caa vs aaa starts with c vs a. c has rank 2 and a has rank 0, so c would come after a. That breaks the pair, and abc is rejected.
4
If no candidate passes, return an empty string.

Visual

Each step is one order of the letters. Red = the order breaks a pair (rejected); purple = the first valid order, returned.

Brute force tries every letter orderwords = ["caa", "aaa", "aab"]step 1/5

order

Candidate

order: abc
check: w0 vs w1: c vs a

abc: c after a breaks the pair

In abc, a comes before c, but the words need c first (index 0 of w0 and w1). Reject this order.

Code & Implementation

brute.cpp

class Solution {
public:
    string findOrder(vector<string>& words) {
        // The letters that appear in some word, in alphabetical order.
        vector<bool> seen(26, false);
        for (const string& w : words)
            for (char c : w) seen[c - 'a'] = true;
        string letters;
        for (int c = 0; c < 26; c++)
            if (seen[c]) letters += char('a' + c);

        // Try every order of those letters. next_permutation visits them all.
        do {
            // rank[c] = where letter c sits in this candidate order.
            vector<int> rank(26, 0);
            for (int i = 0; i < (int)letters.size(); i++) rank[letters[i] - 'a'] = i;
            if (sortedUnder(words, rank)) return letters;
        } while (next_permutation(letters.begin(), letters.end()));
        return "";
    }

private:
    // True if every word is <= the word after it, comparing letters by rank.
    bool sortedUnder(const vector<string>& words, const vector<int>& rank) {
        for (int i = 0; i + 1 < (int)words.size(); i++) {
            const string& a = words[i];
            const string& b = words[i + 1];
            size_t m = min(a.size(), b.size());
            bool decided = false;
            for (size_t j = 0; j < m; j++) {
                if (a[j] != b[j]) {
                    // The first differing letter decides the pair.
                    if (rank[a[j] - 'a'] > rank[b[j] - 'a']) return false;
                    decided = true;
                    break;
                }
            }
            // Same letters up to the shorter length: the shorter word must come first.
            if (!decided && a.size() > b.size()) return false;
        }
        return true;
    }
};

import java.util.*;

class Solution {
    public String findOrder(String[] words) {
        // The letters that appear in some word, in alphabetical order.
        boolean[] seen = new boolean[26];
        for (String w : words) {
            for (char c : w.toCharArray()) seen[c - 'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        for (int c = 0; c < 26; c++) {
            if (seen[c]) sb.append((char) ('a' + c));
        }
        char[] letters = sb.toString().toCharArray();

        // Try every order of those letters. next_permutation visits them all.
        do {
            // rank[c] = where letter c sits in this candidate order.
            int[] rank = new int[26];
            for (int i = 0; i < letters.length; i++) {
                rank[letters[i] - 'a'] = i;
            }
            if (sortedUnder(words, rank)) return new String(letters);
        } while (nextPermutation(letters));
        return "";
    }

    // True if every word is <= the word after it, comparing letters by rank.
    private boolean sortedUnder(String[] words, int[] rank) {
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i];
            String b = words[i + 1];
            int m = Math.min(a.length(), b.length());
            boolean decided = false;
            for (int j = 0; j < m; j++) {
                if (a.charAt(j) != b.charAt(j)) {
                    // The first differing letter decides the pair.
                    if (rank[a.charAt(j) - 'a'] > rank[b.charAt(j) - 'a']) return false;
                    decided = true;
                    break;
                }
            }
            // Same letters up to the shorter length: the shorter word must come first.
            if (!decided && a.length() > b.length()) return false;
        }
        return true;
    }

    private boolean nextPermutation(char[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] >= a[i + 1]) i--;
        if (i < 0) return false;
        int j = a.length - 1;
        while (a[j] <= a[i]) j--;
        char temp = a[i]; a[i] = a[j]; a[j] = temp;
        int l = i + 1, r = a.length - 1;
        while (l < r) {
            temp = a[l]; a[l] = a[r]; a[r] = temp;
            l++; r--;
        }
        return true;
    }
}

from typing import List
from itertools import permutations

class Solution:
    def findOrder(self, words: List[str]) -> str:
        # The letters that appear in some word, in alphabetical order.
        seen = [False] * 26
        for w in words:
            for c in w:
                seen[ord(c) - ord('a')] = True
        letters = [chr(ord('a') + c) for c in range(26) if seen[c]]

        # True if every word is <= the word after it, comparing letters by rank.
        def sorted_under(words: List[str], rank: List[int]) -> bool:
            for i in range(len(words) - 1):
                a = words[i]
                b = words[i + 1]
                m = min(len(a), len(b))
                decided = False
                for j in range(m):
                    if a[j] != b[j]:
                        # The first differing letter decides the pair.
                        if rank[ord(a[j]) - ord('a')] > rank[ord(b[j]) - ord('a')]:
                            return False
                        decided = True
                        break
                # Same letters up to the shorter length: the shorter word must come first.
                if not decided and len(a) > len(b):
                    return False
            return True

        # Try every order of those letters. next_permutation visits them all.
        for perm in permutations(letters):
            rank = [0] * 26
            for i, ch in enumerate(perm):
                rank[ord(ch) - ord('a')] = i
            if sorted_under(words, rank):
                return "".join(perm)
        return ""

export function findOrder(words: string[]): string {
    // The letters that appear in some word, in alphabetical order.
    const seen: boolean[] = new Array(26).fill(false);
    for (const w of words) {
        for (let i = 0; i < w.length; i++) {
            seen[w.charCodeAt(i) - 97] = true;
        }
    }
    const letters: string[] = [];
    for (let c = 0; c < 26; c++) {
        if (seen[c]) letters.push(String.fromCharCode(97 + c));
    }

    // True if every word is <= the word after it, comparing letters by rank.
    function sortedUnder(rank: number[]): boolean {
        for (let i = 0; i + 1 < words.length; i++) {
            const a = words[i];
            const b = words[i + 1];
            const m = Math.min(a.length, b.length);
            let decided = false;
            for (let j = 0; j < m; j++) {
                if (a[j] !== b[j]) {
                    // The first differing letter decides the pair.
                    if (rank[a.charCodeAt(j) - 97] > rank[b.charCodeAt(j) - 97]) return false;
                    decided = true;
                    break;
                }
            }
            // Same letters up to the shorter length: the shorter word must come first.
            if (!decided && a.length > b.length) return false;
        }
        return true;
    }

    function nextPermutation(a: string[]): boolean {
        let i = a.length - 2;
        while (i >= 0 && a[i] >= a[i + 1]) i--;
        if (i < 0) return false;
        let j = a.length - 1;
        while (a[j] <= a[i]) j--;
        const temp = a[i]; a[i] = a[j]; a[j] = temp;
        let l = i + 1, r = a.length - 1;
        while (l < r) {
            const t = a[l]; a[l] = a[r]; a[r] = t;
            l++; r--;
        }
        return true;
    }

    // Try every order of those letters. next_permutation visits them all.
    do {
        // rank[c] = where letter c sits in this candidate order.
        const rank: number[] = new Array(26).fill(0);
        for (let i = 0; i < letters.length; i++) {
            rank[letters[i].charCodeAt(0) - 97] = i;
        }
        if (sortedUnder(rank)) return letters.join("");
    } while (nextPermutation(letters));

    return "";
}

Complexity

Time O(U! · N · L)Space O(U)

U is the number of distinct letters, N is the number of words and L is the longest word. Each candidate order is checked against N − 1 pairs, and each pair costs at most L letter comparisons. Brute force stops early at the first valid order.

Optimized approach

Idea

Start from brute force

Brute force tries whole orders, and each order is checked against every pair again. But each pair only says one thing: its first differing letter gives one rule. So the pairs can be turned into rules once, and the order can be built from the rules.

Find the repeated work

Brute force re-reads every pair for every candidate order, although each pair's answer never changes. Most candidates fail on the same pair, and the work is repeated for each one.

Define the state — what variables do I need?

rules: One arrow x → y for each neighbouring pair's first differing letter. Each arrow is stored once.
in: For each letter, how many arrows point into it. A letter with in = 0 has nothing that must come before it.
queue, order: The letters that are ready to place, and the answer built so far.

Define validity

A letter can be placed next only when every arrow pointing into it has already been placed. Then no rule is broken, because nothing unplaced must come before it.

Define the transitions — when does each pointer move, and why is it safe?

For each neighbouring pair, once

Find the first index where the letters differ. Add the arrow a[i] → b[i] if it is not there yet, and increase in[b[i]].

That single comparison is all the sorted order says about this pair. Letters after the difference are not forced, so they must not add arrows.

Before the loop

Queue every letter that appears with in = 0.

These letters have nothing before them, so they can go first. Letters with no arrows at all are in this group too.

Each pop

Append the letter to the order. For each arrow out of it, lower the target's in by 1, and queue the target when it reaches 0.

Removing a placed letter removes exactly its arrows. A letter that reaches 0 has no unplaced letter in front of it.

What does the current window add to the answer?

Each popped letter adds one letter to the end of the order. Every letter is popped once, so the final string holds each letter exactly once.

Code & Implementation

optimal.cpp

class Solution {
public:
    string findOrder(vector<string>& words) {
        // Only letters that appear in some word take part in the answer.
        vector<bool> appears(26, false);
        for (const string& w : words)
            for (char c : w) appears[c - 'a'] = true;

        // Compare each adjacent pair, but stop at the FIRST differing letter.
        // after[u][v] = true means u must come before v. A table keeps each rule once.
        vector<vector<bool>> after(26, vector<bool>(26, false));
        vector<int> indeg(26, 0);
        for (int i = 0; i + 1 < (int)words.size(); i++) {
            const string& a = words[i];
            const string& b = words[i + 1];
            size_t m = min(a.size(), b.size());
            size_t j = 0;
            while (j < m && a[j] == b[j]) j++;
            if (j == m) {
                // No differing letter: a prefix must come first, so a longer word cannot be first.
                if (a.size() > b.size()) return "";
                continue;
            }
            int u = a[j] - 'a', v = b[j] - 'a';
            if (!after[u][v]) {
                after[u][v] = true;
                indeg[v]++;
            }
        }

        // Kahn: start from every letter that appears and has no rule pointing at it.
        // Letters with no rules at all have in-degree 0, so they are included too.
        queue<int> q;
        int total = 0;
        for (int c = 0; c < 26; c++) {
            if (!appears[c]) continue;
            total++;
            if (indeg[c] == 0) q.push(c);
        }
        string order;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order += char('a' + u);
            for (int v = 0; v < 26; v++)
                if (after[u][v] && --indeg[v] == 0) q.push(v);
        }
        // A cycle leaves some letters with in-degree > 0 forever, so fewer letters come out.
        return (int)order.size() == total ? order : "";
    }
};

import java.util.*;

class Solution {
    public String findOrder(String[] words) {
        // Only letters that appear in some word take part in the answer.
        boolean[] appears = new boolean[26];
        for (String w : words) {
            for (char c : w.toCharArray()) appears[c - 'a'] = true;
        }

        // Compare each adjacent pair, but stop at the FIRST differing letter.
        // after[u][v] = true means u must come before v. A table keeps each rule once.
        boolean[][] after = new boolean[26][26];
        int[] indeg = new int[26];
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i];
            String b = words[i + 1];
            int m = Math.min(a.length(), b.length());
            int j = 0;
            while (j < m && a.charAt(j) == b.charAt(j)) j++;
            if (j == m) {
                // No differing letter: a prefix must come first, so a longer word cannot be first.
                if (a.length() > b.length()) return "";
                continue;
            }
            int u = a.charAt(j) - 'a', v = b.charAt(j) - 'a';
            if (!after[u][v]) {
                after[u][v] = true;
                indeg[v]++;
            }
        }

        // Kahn: start from every letter that appears and has no rule pointing at it.
        // Letters with no rules at all have in-degree 0, so they are included too.
        Queue<Integer> q = new ArrayDeque<>();
        int total = 0;
        for (int c = 0; c < 26; c++) {
            if (!appears[c]) continue;
            total++;
            if (indeg[c] == 0) q.offer(c);
        }
        StringBuilder order = new StringBuilder();
        while (!q.isEmpty()) {
            int u = q.poll();
            order.append((char) ('a' + u));
            for (int v = 0; v < 26; v++) {
                if (after[u][v] && --indeg[v] == 0) q.offer(v);
            }
        }
        // A cycle leaves some letters with in-degree > 0 forever, so fewer letters come out.
        return order.length() == total ? order.toString() : "";
    }
}

from typing import List
from collections import deque

class Solution:
    def findOrder(self, words: List[str]) -> str:
        # Only letters that appear in some word take part in the answer.
        appears = [False] * 26
        for w in words:
            for c in w:
                appears[ord(c) - ord('a')] = True

        # Compare each adjacent pair, but stop at the FIRST differing letter.
        # after[u][v] = True means u must come before v. A table keeps each rule once.
        after = [[False] * 26 for _ in range(26)]
        indeg = [0] * 26
        for i in range(len(words) - 1):
            a = words[i]
            b = words[i + 1]
            m = min(len(a), len(b))
            j = 0
            while j < m and a[j] == b[j]:
                j += 1
            if j == m:
                # No differing letter: a prefix must come first, so a longer word cannot be first.
                if len(a) > len(b):
                    return ""
                continue
            u, v = ord(a[j]) - ord('a'), ord(b[j]) - ord('a')
            if not after[u][v]:
                after[u][v] = True
                indeg[v] += 1

        # Kahn: start from every letter that appears and has no rule pointing at it.
        # Letters with no rules at all have in-degree 0, so they are included too.
        q = deque([c for c in range(26) if appears[c] and indeg[c] == 0])
        total = sum(1 for c in range(26) if appears[c])

        order: List[str] = []
        while q:
            u = q.popleft()
            order.append(chr(ord('a') + u))
            for v in range(26):
                if after[u][v]:
                    indeg[v] -= 1
                    if indeg[v] == 0:
                        q.append(v)

        # A cycle leaves some letters with in-degree > 0 forever, so fewer letters come out.
        return "".join(order) if len(order) == total else ""

export function findOrder(words: string[]): string {
    // Only letters that appear in some word take part in the answer.
    const appears: boolean[] = new Array(26).fill(false);
    for (const w of words) {
        for (let i = 0; i < w.length; i++) {
            appears[w.charCodeAt(i) - 97] = true;
        }
    }

    // Compare each adjacent pair, but stop at the FIRST differing letter.
    // after[u][v] = true means u must come before v. A table keeps each rule once.
    const after: boolean[][] = Array.from({ length: 26 }, () => new Array(26).fill(false));
    const indeg: number[] = new Array(26).fill(0);
    for (let i = 0; i + 1 < words.length; i++) {
        const a = words[i];
        const b = words[i + 1];
        const m = Math.min(a.length, b.length);
        let j = 0;
        while (j < m && a[j] === b[j]) j++;
        if (j === m) {
            // No differing letter: a prefix must come first, so a longer word cannot be first.
            if (a.length > b.length) return "";
            continue;
        }
        const u = a.charCodeAt(j) - 97;
        const v = b.charCodeAt(j) - 97;
        if (!after[u][v]) {
            after[u][v] = true;
            indeg[v]++;
        }
    }

    // Kahn: start from every letter that appears and has no rule pointing at it.
    // Letters with no rules at all have in-degree 0, so they are included too.
    const q: number[] = [];
    let total = 0;
    for (let c = 0; c < 26; c++) {
        if (!appears[c]) continue;
        total++;
        if (indeg[c] === 0) q.push(c);
    }

    const order: string[] = [];
    let head = 0;
    while (head < q.length) {
        const u = q[head++];
        order.push(String.fromCharCode(97 + u));
        for (let v = 0; v < 26; v++) {
            if (after[u][v]) {
                indeg[v]--;
                if (indeg[v] === 0) q.push(v);
            }
        }
    }
    // A cycle leaves some letters with in-degree > 0 forever, so fewer letters come out.
    return order.length === total ? order.join("") : "";
}

Complexity

Time O(N · L)Space O(1)

N is the number of words and L is the longest word. Each pair is compared once, in at most L letters. The graph has at most 26 letters, so the 26 × 26 rule table and the Kahn loop are fixed size.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try each order of the letters; keep the first one that sorts the list	O(U! · N · L)	O(U)
Optimal	One rule per neighbouring pair; then place letters that have nothing before them	O(N · L)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“words sorted in an alien language”The sorted list hides a set of letter comparisons. Build the graph from them, then sort it.
“return any valid order”This is a topological sort: any order that puts every arrow's tail before its head.
“empty string if no order”A cycle makes Kahn stop early, so the count of placed letters tells us.

neighbouring pairs+first differing letter = one rule+topological order of the letters→Topological Sort — Build the graph, then sort (Kahn's algorithm)

The graph is hidden: the words only say which letter comes first in each neighbouring pair. Each pair gives one rule, from its first differing letter. Letters after that point are never compared for a rule, so the first difference is all you read. The next question, Alien Dictionary, keeps this rule and adds the prefix case and the letters that have no rules.

Don't make this mistake

Reading past the first difference (string-diff habit)

✗ for (size_t j = 0; j < m; j++) if (a[j] != b[j]) addRule(a[j], b[j]); // keeps going

✓ for (size_t j = 0; j < m; j++) if (a[j] != b[j]) { addRule(a[j], b[j]); break; }

A string diff marks every mismatch, but a sorted list only decides the pair at its first mismatch. On ["ab", "ca", "cb"], the pair ab vs ca gives a → c at index 0. Reading on gives b vs a at index 1, a false arrow b → a. Together with a → b from ca vs cb, that is a cycle, so the code returns "". But "acb" is a valid answer.

Returning the partial order when a cycle stops Kahn

✗ return order;

✓ return (int)order.size() == total ? order : "";

On ["d", "ab", "ba", "ab"], the rules are d → a, a → b and b → a. Kahn places d, then a and b wait on each other. The queue is empty with 1 of 3 letters placed. Returning "d" is wrong: the answer must be empty.

Comparing the whole words instead of neighbours

Comparing every pair of words adds rules that the neighbouring pairs already imply, so the answer is still right but the work grows with N². Only neighbours are needed: a sorted list is sorted as soon as each neighbouring pair is in order.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Alien Dictionary