Alien Dictionary Character Order

The Alien Dictionary problem asks: Given a sorted dictionary of an alien language containing N words and K unique starting characters (from a known alphabet), determine the correct order of characters in the alien language.

The words are sorted lexicographically according to the rules of the alien language. By comparing adjacent words, we can derive the ordering of some characters. Our goal is to derive a valid total character order that satisfies all such pairwise orderings.

Note: Multiple valid orders may exist for the same input.

Understanding the Problem

We are given a list of words that are sorted lexicographically according to the rules of an unknown language. Our task is to determine the correct order of characters in this alien language based on the order of words. The key idea is that the character order must satisfy the relative positions of characters as implied by the word list.

This is a classic case of extracting a topological ordering of characters from the word relationships.

Step-by-Step Solution with Example

step 1: Understand what the input means

Suppose the input is a list of words like [ "baa", "abcd", "abca", "cab", "cad" ]. These words are sorted in an alien language. From this, we need to find the character order of that alien alphabet.

step 2: Build a graph of characters

Each unique character will be a node in a graph. By comparing adjacent words, we extract ordering rules. For example:

• Compare "baa" and "abcd" → 'b' vs 'a' → since 'b' ≠ 'a', we know 'b' comes before 'a' → add edge b → a.
• Compare "abcd" and "abca" → 'd' vs 'a' → 'd' comes before 'a' → add edge d → a.
• Compare "abca" and "cab" → 'a' vs 'c' → 'a' comes before 'c' → add edge a → c.
• Compare "cab" and "cad" → 'b' vs 'd' → 'b' comes before 'd' → add edge b → d.

step 3: Prepare in-degrees for topological sort

We calculate the in-degree (number of incoming edges) for each node (character). This helps identify nodes with no dependencies — these can appear first in the alien order.

step 4: Topological Sorting using Kahn’s Algorithm

Start with characters having in-degree 0. Add them to a queue and begin removing them one by one, appending to the result string and decreasing the in-degree of their neighbors. If a neighbor's in-degree becomes 0, add it to the queue.

step 5: Check for cycle

If at the end of this process, our result contains fewer characters than expected, then there is a cycle (conflicting character ordering), and we cannot determine a valid order.

step 6: Return the result

The result string formed by topological sort will represent the correct character order in the alien language if no cycle exists.

Edge Cases

• Prefix issue: If a word is a prefix of a longer word and comes later (e.g., “apple” before “app”), this is invalid. We should detect this and return an empty result.
• Disconnected characters: If a character appears in the word list but no ordering info is derived from it, we still need to include it in the result.
• Duplicate words: Should be ignored as they give no additional info.
• Single word input: We can return any order of the unique characters in that word.

Finally

This problem is a combination of graph building and topological sorting. By carefully comparing adjacent words and constructing a graph of character dependencies, we can extract a valid character order for the alien language. Kahn’s algorithm is particularly useful because it also helps detect cycles (invalid inputs). Always consider edge cases like prefix conflicts and disconnected components to build a robust solution.

1. Initialize an adjacency list and an in-degree map for all K characters.
2. Compare each pair of adjacent words to extract precedence rules (edges).
3. Build the graph and update the in-degrees of each character.
4. Use a queue to perform BFS (Kahn’s algorithm):
   1. Push characters with in-degree 0 into the queue.
   2. Pop from queue, add to result string.
   3. Decrease in-degrees of neighbors, and push those with 0 in-degree.
5. If the result string has length K, return it as the answer. Otherwise, input had a cycle or inconsistency.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 26

void alienOrder(char* words[], int n, int k) {
    int adj[MAX][MAX] = {0};
    int indegree[MAX] = {0};

    for (int i = 0; i < n - 1; i++) {
        char* w1 = words[i];
        char* w2 = words[i + 1];
        int len = strlen(w1) < strlen(w2) ? strlen(w1) : strlen(w2);
        for (int j = 0; j < len; j++) {
            if (w1[j] != w2[j]) {
                int u = w1[j] - 'a';
                int v = w2[j] - 'a';
                if (!adj[u][v]) {
                    adj[u][v] = 1;
                    indegree[v]++;
                }
                break;
            }
        }
    }

    char queue[MAX];
    int front = 0, rear = 0;
    for (int i = 0; i < k; i++) {
        if (indegree[i] == 0) queue[rear++] = i;
    }

    while (front < rear) {
        int u = queue[front++];
        printf("%c", u + 'a');
        for (int v = 0; v < k; v++) {
            if (adj[u][v]) {
                if (--indegree[v] == 0) queue[rear++] = v;
            }
        }
    }
    printf("\n");
}

int main() {
    char* words[] = {"caa", "aaa", "aab"};
    int n = 3;
    int k = 3;
    printf("Order: ");
    alienOrder(words, n, k);
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

string alienOrder(vector<string>& words, int k) {
    vector<vector<int>> adj(k);
    vector<int> indegree(k, 0);

    for (int i = 0; i < words.size() - 1; i++) {
        string w1 = words[i], w2 = words[i + 1];
        int len = min(w1.size(), w2.size());
        for (int j = 0; j < len; j++) {
            if (w1[j] != w2[j]) {
                adj[w1[j] - 'a'].push_back(w2[j] - 'a');
                indegree[w2[j] - 'a']++;
                break;
            }
        }
    }

    queue<int> q;
    for (int i = 0; i < k; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    string result;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result += (char)(u + 'a');
        for (int v : adj[u]) {
            if (--indegree[v] == 0) q.push(v);
        }
    }
    return result.size() == k ? result : "";
}

int main() {
    vector<string> words = {"caa", "aaa", "aab"};
    int k = 3;
    cout << "Order: " << alienOrder(words, k) << endl;
    return 0;
}

from collections import defaultdict, deque

def alien_order(words, k):
    adj = defaultdict(list)
    indegree = [0] * k

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i+1]
        for j in range(min(len(w1), len(w2))):
            if w1[j] != w2[j]:
                u, v = ord(w1[j]) - ord('a'), ord(w2[j]) - ord('a')
                adj[u].append(v)
                indegree[v] += 1
                break

    queue = deque([i for i in range(k) if indegree[i] == 0])
    result = []
    while queue:
        u = queue.popleft()
        result.append(chr(u + ord('a')))
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return ''.join(result) if len(result) == k else ""

print("Order:", alien_order(["caa", "aaa", "aab"], 3))

import java.util.*;

public class AlienDictionary {
    public static String alienOrder(String[] words, int k) {
        List<Integer>[] adj = new ArrayList[k];
        int[] indegree = new int[k];
        for (int i = 0; i < k; i++) adj[i] = new ArrayList<>();

        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i + 1];
            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    int u = w1.charAt(j) - 'a';
                    int v = w2.charAt(j) - 'a';
                    adj[u].add(v);
                    indegree[v]++;
                    break;
                }
            }
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < k; i++) if (indegree[i] == 0) q.add(i);

        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            int u = q.poll();
            sb.append((char)(u + 'a'));
            for (int v : adj[u]) {
                if (--indegree[v] == 0) q.add(v);
            }
        }
        return sb.length() == k ? sb.toString() : "";
    }

    public static void main(String[] args) {
        String[] words = {"caa", "aaa", "aab"};
        int k = 3;
        System.out.println("Order: " + alienOrder(words, k));
    }
}

function alienOrder(words, k) {
  const adj = Array.from({ length: k }, () => []);
  const indegree = new Array(k).fill(0);

  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    const minLen = Math.min(w1.length, w2.length);

    for (let j = 0; j < minLen; j++) {
      if (w1[j] !== w2[j]) {
        adj[w1.charCodeAt(j) - 97].push(w2.charCodeAt(j) - 97);
        indegree[w2.charCodeAt(j) - 97]++;
        break;
      }
    }
  }

  const queue = [];
  for (let i = 0; i < k; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  const order = [];
  while (queue.length > 0) {
    const u = queue.shift();
    order.push(String.fromCharCode(u + 97));
    for (const v of adj[u]) {
      indegree[v]--;
      if (indegree[v] === 0) queue.push(v);
    }
  }
  return order.length === k ? order.join('') : "";
}

console.log("Order:", alienOrder(["caa","aaa","aab"], 3));

package main

import (
    "fmt"
)

func alienOrder(words []string, k int) string {
    adj := make([][]int, k)
    indegree := make([]int, k)
    for i := range adj {
        adj[i] = []int{}
    }

    for i := 0; i < len(words)-1; i++ {
        w1, w2 := words[i], words[i+1]
        minLen := len(w1)
        if len(w2) < minLen {
            minLen = len(w2)
        }
        for j := 0; j < minLen; j++ {
            if w1[j] != w2[j] {
                u := int(w1[j] - 'a')
                v := int(w2[j] - 'a')
                adj[u] = append(adj[u], v)
                indegree[v]++
                break
            }
        }
    }

    queue := []int{}
    for i := 0; i < k; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    result := ""
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        result += string(rune(u + 'a'))
        for _, v := range adj[u] {
            indegree[v]--
            if indegree[v] == 0 {
                queue = append(queue, v)
            }
        }
    }
    if len(result) == k {
        return result
    }
    return ""
}

func main() {
    words := []string{"caa", "aaa", "aab"}
    fmt.Println("Order:", alienOrder(words, 3))
}

use std::collections::{VecDeque, HashMap};

fn alien_order(words: Vec<&str>, k: usize) -> String {
    let mut adj = vec![vec![]; k];
    let mut indegree = vec![0; k];

    for i in 0..words.len() - 1 {
        let w1 = words[i].as_bytes();
        let w2 = words[i + 1].as_bytes();
        let len = w1.len().min(w2.len());
        for j in 0..len {
            if w1[j] != w2[j] {
                let u = (w1[j] - b'a') as usize;
                let v = (w2[j] - b'a') as usize;
                adj[u].push(v);
                indegree[v] += 1;
                break;
            }
        }
    }

    let mut queue = VecDeque::new();
    for i in 0..k {
        if indegree[i] == 0 {
            queue.push_back(i);
        }
    }

    let mut result = String::new();
    while let Some(u) = queue.pop_front() {
        result.push((u as u8 + b'a') as char);
        for &v in &adj[u] {
            indegree[v] -= 1;
            if indegree[v] == 0 {
                queue.push_back(v);
            }
        }
    }

    if result.len() == k {
        result
    } else {
        "".to_string()
    }
}

fn main() {
    let words = vec!["caa", "aaa", "aab"];
    println!("Order: {}", alien_order(words, 3));
}

fun alienOrder(words: Array<String>, k: Int): String {
    val adj = Array(k) { mutableListOf<Int>() }
    val indegree = IntArray(k)

    for (i in 0 until words.size - 1) {
        val w1 = words[i]
        val w2 = words[i + 1]
        for (j in 0 until minOf(w1.length, w2.length)) {
            if (w1[j] != w2[j]) {
                val u = w1[j] - 'a'
                val v = w2[j] - 'a'
                adj[u].add(v)
                indegree[v]++
                break
            }
        }
    }

    val queue = ArrayDeque<Int>()
    for (i in 0 until k) if (indegree[i] == 0) queue.add(i)

    val result = StringBuilder()
    while (queue.isNotEmpty()) {
        val u = queue.removeFirst()
        result.append((u + 'a'.code).toChar())
        for (v in adj[u]) {
            indegree[v]--
            if (indegree[v] == 0) queue.add(v)
        }
    }
    return if (result.length == k) result.toString() else ""
}

fun main() {
    val words = arrayOf("caa", "aaa", "aab")
    println("Order: ${alienOrder(words, 3)}")
}

func alienOrder(_ words: [String], _ k: Int) -> String {
    var adj = Array(repeating: [Int](), count: k)
    var indegree = Array(repeating: 0, count: k)

    for i in 0..<words.count-1 {
        let w1 = Array(words[i]), w2 = Array(words[i+1])
        for j in 0..<min(w1.count, w2.count) {
            if w1[j] != w2[j] {
                let u = Int(w1[j].asciiValue! - Character("a").asciiValue!)
                let v = Int(w2[j].asciiValue! - Character("a").asciiValue!)
                adj[u].append(v)
                indegree[v] += 1
                break
            }
        }
    }

    var queue = [Int]()
    for i in 0..<k where indegree[i] == 0 {
        queue.append(i)
    }

    var result = ""
    while !queue.isEmpty {
        let u = queue.removeFirst()
        result += String(UnicodeScalar(u + 97)!)
        for v in adj[u] {
            indegree[v] -= 1
            if indegree[v] == 0 {
                queue.append(v)
            }
        }
    }

    return result.count == k ? result : ""
}

let words = ["caa", "aaa", "aab"]
print("Order: \(alienOrder(words, 3))")

function alienOrder(words: string[], k: number): string {
  const adj: number[][] = Array.from({ length: k }, () => []);
  const indegree: number[] = new Array(k).fill(0);

  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    const len = Math.min(w1.length, w2.length);

    for (let j = 0; j < len; j++) {
      if (w1[j] !== w2[j]) {
        const u = w1.charCodeAt(j) - 97;
        const v = w2.charCodeAt(j) - 97;
        adj[u].push(v);
        indegree[v]++;
        break;
      }
    }
  }

  const queue: number[] = [];
  for (let i = 0; i < k; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  const result: string[] = [];
  while (queue.length > 0) {
    const u = queue.shift()!;
    result.push(String.fromCharCode(u + 97));
    for (const v of adj[u]) {
      indegree[v]--;
      if (indegree[v] === 0) queue.push(v);
    }
  }
  return result.length === k ? result.join('') : "";
}

console.log("Order:", alienOrder(["caa", "aaa", "aab"], 3));

Time complexity

Space complexity

O(K + E)

We store an adjacency list for up to K characters and E edges (from character precedence rules), and also track in-degree for K nodes.