Skip to content

Decoding the Alien Script

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 1 (Click for link to problem statements)

Decoding the Alien Script

Archaeologists found a list of words words already sorted according to some unknown alphabet's ordering. From this ordering you can deduce the relative order of the letters.

Return a string of the letters in a valid order for that alphabet. If several orders are valid, any one is acceptable; return "" if the ordering is contradictory.

def alien_order(words):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Graphs, Topological Sort, BFS (Kahn's Algorithm)

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: How do we deduce the relative order of two letters from the sorted word list?

    • A: Compare each adjacent pair of words and find the first position where they differ. The letter from the earlier word comes before the letter from the later word in the alien alphabet. Letters after the first difference tell us nothing.

  • Q: What makes an ordering contradictory?

    • A: Two things: (1) the deduced rules form a cycle (e.g. a before b and b before a), or (2) a longer word appears before its own prefix (e.g. "abc" before "ab"), which no alphabet can justify. Both cases return "".

  • Q: Which letters must appear in the answer?

    • A: Every distinct letter that appears anywhere in words, even letters with no ordering rules attached — those can go anywhere in the output.
HAPPY CASE
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Explanation: "wrt" vs "wrf" gives t < f; "wrf" vs "er" gives w < e; "er" vs "ett" gives r < t; "ett" vs "rftt" gives e < r. Chaining the rules yields w, e, r, t, f.

Input: words = ["z", "x"]
Output: "zx"
Explanation: The only rule is z < x, so "zx" is a valid order.

EDGE CASE
Input: words = ["z", "x", "z"]
Output: ""
Explanation: The rules z < x and x < z form a cycle, so the ordering is contradictory.

Input: words = ["abc", "ab"]
Output: ""
Explanation: A longer word appears before its own prefix, which is impossible in any alphabet.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Ordering with Dependency Constraints, we can consider the following approaches:

  • Topological Sort: Each deduced rule "letter a comes before letter b" is a directed edge a -> b. A valid alphabet is exactly a topological ordering of this graph, and a cycle means no valid order exists.
  • BFS (Kahn's Algorithm): Repeatedly output letters with no remaining prerequisites (in-degree 0), removing their outgoing edges as we go. If some letters are never output, the graph has a cycle.
  • DFS with post-order: An alternative topological sort that appends letters after visiting all their dependents, detecting cycles with a three-state visited marker.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Build a directed graph over the distinct letters. For each adjacent pair of words, the first differing character produces one edge; a pair with no differing character is only legal if the first word is not longer than the second. Then run Kahn's algorithm: seed a queue with all in-degree-0 letters, pop letters into the answer, and decrement neighbors' in-degrees. If the answer ends up shorter than the number of distinct letters, a cycle exists and we return "".

1) Collect every distinct letter in `words`; give each an empty adjacency set and in-degree 0.
2) For each adjacent pair of words (first, second):
   a) Walk both words together until the characters differ.
   b) At the first difference (a, b): add edge a -> b if it is new, and increment in-degree of b.
   c) If no difference is found and first is longer than second, return "" immediately.
3) Initialize a queue with every letter whose in-degree is 0.
4) While the queue is not empty:
   a) Pop a letter and append it to the result.
   b) For each neighbor, decrement its in-degree; enqueue it when it reaches 0.
5) If the result contains fewer letters than the graph, return "" (cycle detected).
6) Otherwise, join the result into a string and return it.

⚠️ Common Mistakes

  • Comparing every pair of words instead of only adjacent pairs — only adjacent pairs in a sorted list carry direct ordering information.
  • Deriving rules from characters after the first difference; only the first differing position is meaningful.
  • Adding the same edge twice (e.g. two word pairs implying t < f), which inflates the in-degree and strands letters in the queue.
  • Forgetting the prefix check, so ["abc", "ab"] incorrectly returns an ordering instead of "".
  • Forgetting to include letters that never appear in any rule — they still belong in the output.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def alien_order(words):
    # Build a graph over every letter that appears in the word list
    adjacency = {char: set() for word in words for char in word}
    in_degree = {char: 0 for char in adjacency}

    # Compare each adjacent pair of words to extract one ordering rule
    for first, second in zip(words, words[1:]):
        for char_a, char_b in zip(first, second):
            if char_a != char_b:
                if char_b not in adjacency[char_a]:
                    adjacency[char_a].add(char_b)
                    in_degree[char_b] += 1
                break
        else:
            # No differing letter found: invalid if the longer word comes first
            if len(first) > len(second):
                return ""

    # Kahn's algorithm: repeatedly remove letters with no remaining prerequisites
    queue = deque(char for char in in_degree if in_degree[char] == 0)
    order = []
    while queue:
        char = queue.popleft()
        order.append(char)
        for neighbor in adjacency[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If any letter never reached in-degree 0, the rules form a cycle
    if len(order) < len(in_degree):
        return ""
    return "".join(order)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: words = ["wrt", "wrf", "er", "ett", "rftt"]

    • Edges deduced: t -> f, w -> e, r -> t, e -> r.
    • In-degrees: w:0, e:1, r:1, t:1, f:1, so the queue starts with only w.
    • Pop w (frees e), pop e (frees r), pop r (frees t), pop t (frees f), pop f.
    • Output: "wertf"

  • Input: words = ["z", "x", "z"]

    • Edges deduced: z -> x and x -> z; both letters keep in-degree 1, so the queue starts empty.
    • The loop outputs nothing, len(order) = 0 < 2 letters.
    • Output: ""

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

    • The pair has no differing character and len("abc") > len("ab"), so the prefix check fires.
    • Output: ""

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume C is the total number of characters across all words, V is the number of distinct letters, and E is the number of deduced ordering rules (edges).

  • Time Complexity: O(C) to build the graph, since each adjacent word comparison is bounded by the words' lengths, plus O(V + E) for Kahn's algorithm — O(C) overall because V and E are both bounded by C.
  • Space Complexity: O(V + E) for the adjacency sets, in-degree map, and queue — at worst O(V^2) edges for a fixed-size alphabet, which is effectively O(1) when the alphabet is bounded (e.g. 26 lowercase letters).

Clone this wiki locally