Alien Dictionary

+10

A list of words is sorted in an alphabet you do not know: the 26 lowercase English letters in some secret order. Words compare the usual way. The first position where two words differ decides, by which of the two letters comes first in the alphabet, and when one word is the start of the other, the shorter word comes first.

Return the letters that appear in the words, as one string in alphabet order. When several orders fit the list, return the one that comes first in ordinary dictionary order. When no order fits, return "invalid".

Function

alienOrder(words: string-array) → string

wordsstring-array: the words, sorted in the unknown alphabet
Returnsstring: the letters in the smallest order that fits, or "invalid"

Constraints

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Every word contains only lowercase English letters.
The same word may appear more than once.

Examples

Input: words = ["tea", "ten", "ate", "act", "cat"]
Output: "etacn"
Explanation: tea and ten first differ at a and n, so a comes before n. The other pairs give t before a, t before c and a before c. No rule mentions e, so the smallest order puts it first, then t, then a, then c and n, which are both free by then, with c first.

Input: words = ["bat", "tab", "tub", "bus"]
Output: "invalid"
Explanation: bat before tab puts b before t, tab before tub puts a before u, and tub before bus puts t before b. b before t and t before b cannot both hold, so no order fits.

Input: words = ["cooking", "cook"]
Output: "invalid"
Explanation: cook is the start of cooking, so in every alphabet it comes first. The list puts it second, which no order of the letters can explain.

+20 hidden tests on Submit

Follow-up

How would you tell whether the fitting order is the only one?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The list hides its alphabet in the places where neighbouring words first differ. Each such place gives one rule, letter x before letter y, and the rules form a directed graph on the letters. A fitting order is a topological order of that graph. Two things make the list impossible: a cycle among the rules, and a word placed before its own prefix. Placing the smallest available letter at every step, with a min-heap, gives the smallest fitting order.

Try every order of the letters

Correct, but does not finish on the largest tests

Intuition

The answer is some arrangement of the k distinct letters. You can test one arrangement directly: the list fits it when every pair of neighbouring words is in order under it. Compare the two words at the first position where they differ; the first word's letter must come earlier in the arrangement. If they never differ, the first word must not be longer. Neighbours are enough, because being sorted is a chain: if each word is at most the next one, the whole list is sorted.

Now walk the arrangements from smallest to largest. Start from the letters in alphabetical order, which is the smallest arrangement of all, and step to the next larger one each time (the next permutation). The first arrangement that passes the test is the smallest order that fits. If none passes, return "invalid".

This is correct, and hopeless on real input. k letters have k! arrangements: 5 letters give 120, 10 give 3,628,800, and all 26 give about 4 × 10^26. Each test reads the whole list, C characters in all and up to 5 × 10^4. In the large tests the smallest fitting order starts with f or z, so an astronomical number of arrangements comes before it, and when nothing fits the search has to try every one.

Algorithm

Collect the distinct letters and sort them alphabetically.
Record each letter's position (its rank) in the current arrangement.
Check every neighbouring pair: at the first differing position the first word's letter needs the smaller rank; with no differing position the first word must not be longer.
If every pair passes, return the arrangement. Otherwise move to the next larger arrangement.
When there is no next arrangement, return "invalid".

from itertools import permutations


def fits(words, rank):
    # The list is sorted under rank when every neighbouring pair is in order.
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                if rank[x] > rank[y]:
                    return False
                break
        else:
            # One word starts the other: the shorter must come first.
            if len(first) > len(second):
                return False
    return True


def alienOrder(words):
    letters = sorted(set("".join(words)))
    # permutations() of a sorted list yields the orders from smallest to largest,
    # so the first order that fits is the answer.
    for order in permutations(letters):
        rank = {ch: i for i, ch in enumerate(order)}
        if fits(words, rank):
            return "".join(order)
    return "invalid"

Kahn's algorithm with a min-heap

Intuition

Read the rules out of the list instead of guessing orders. Take two neighbouring words and find the first position where they differ. tea and ten agree on t and e and differ at a and n, so a comes before n. That is the whole message of the pair. The letters after the first difference say nothing: act comes before cat because a comes before c, and the c and t that follow in act are never compared with the a and t of cat. So each pair gives at most one rule, an edge from one letter to another.

A pair with no differing position is the prefix trap. One word is the start of the other, and the shorter must come first in any alphabet. cook before cooking is fine and gives no rule. cooking before cook can never be sorted, so return "invalid" at once. A loop that only looks for differing letters finds nothing in this pair and goes on to return an order for a list no alphabet can produce.

Now you need an order of the letters that respects every edge, a topological order. Kahn's algorithm builds one. Count the edges pointing at each letter (its indegree), place a letter whose count is 0, remove its outgoing edges, and repeat. A letter on a cycle always keeps an edge from the letter before it on the cycle, so its count never reaches 0 and it is never placed. If fewer letters are placed than appear in the words, there is a cycle, and the answer is "invalid".

To get the smallest order, keep the letters whose count is 0 in a min-heap and always place the smallest. This greedy choice is safe. The first letter of any fitting order has count 0, so the smallest ready letter is the smallest possible first letter. Placing it removes edges and never blocks another letter: every letter that was ready stays ready. The same argument then applies to the second position, and so on. In the first example e and t are both ready at the start, and e goes first. A plain queue would also give a valid order, but not always the smallest.

The cost is one pass over the list, C characters in all, to find the first differences. With k ≤ 26 letters there are at most k² edges, kept in a k by k table so a repeated rule is stored once, and the heap never holds more than k letters. That is O(C + k²) time, a few milliseconds on the largest tests.

Algorithm

Mark every letter that appears in the words.
For each pair of neighbouring words, find the first differing position. If there is one, add the edge from the first word's letter to the second word's letter, once. If there is none and the first word is longer, return "invalid".
Count each letter's incoming edges and push every letter that appears and has count 0 onto a min-heap.
Pop the smallest letter and append it. Lower the count of each letter it points to, and push any whose count reaches 0.
If fewer letters were placed than appear, return "invalid". Otherwise return the placed letters.

import heapq


def alienOrder(words):
    # Letters are numbered 0 for 'a' up to 25 for 'z'.
    present = [False] * 26
    for word in words:
        for ch in word:
            present[ord(ch) - 97] = True
    # before[a][b] is True once you know letter a comes before letter b.
    before = [[False] * 26 for _ in range(26)]
    indegree = [0] * 26
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                # Only the first difference tells you anything.
                a, b = ord(x) - 97, ord(y) - 97
                if not before[a][b]:
                    before[a][b] = True
                    indegree[b] += 1
                break
        else:
            # No difference: one word starts the other, so the shorter must come first.
            if len(first) > len(second):
                return "invalid"
    # A min-heap of the letters with nothing left before them.
    heap = [c for c in range(26) if present[c] and indegree[c] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        c = heapq.heappop(heap)
        order.append(chr(c + 97))
        for nxt in range(26):
            if before[c][nxt]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    heapq.heappush(heap, nxt)
    # A letter on a cycle never gets down to indegree 0, so it is never placed.
    if len(order) < sum(present):
        return "invalid"
    return "".join(order)

Pitfalls and edge cases

Most wrong answers here are silent: a misread rule still produces some order, only the wrong one.

Taking more than one rule from a pair. Only the first differing position counts. act before cat says a before c and nothing about the letters after it.
Missing the prefix trap. cooking before cook has no differing letter, so a loop that only handles differences sees nothing and returns an order. The answer is "invalid".
Leaving out letters that appear in no rule. In the first example no rule mentions e, yet it belongs in the answer, and the smallest order puts it first.
Using a plain queue instead of a min-heap. Kahn's algorithm with a queue returns a valid order, but the contract asks for the smallest one.
Counting a repeated rule twice in the indegree but storing it once in the graph. The letter then never reaches 0, and a valid list is reported as a cycle. Store each rule once, or add and remove it the same number of times.
Treating two equal neighbouring words as the prefix trap. A word followed by the same word is in order; only a longer word before its own prefix is impossible.

Frequently asked questions4

What is the time complexity of Alien Dictionary?

O(C + k²), where C is the total number of characters in the words and k ≤ 26 is the number of distinct letters. One pass over the list finds the first difference of every neighbouring pair, and Kahn's algorithm visits at most k² edges. The min-heap adds O(k log k), which is small next to the rest. The edge table takes O(k²) space.

Why compare only neighbouring words?

Being sorted is transitive: if every word is at most the next one, the whole list is sorted. So any rule you could read from two distant words already follows from the neighbouring pairs between them. Comparing every pair of words adds no information and costs O(n²) comparisons instead of n-1.

Why does picking the smallest ready letter give the smallest order?

Any fitting order has to start with a letter that no rule points at. The smallest such letter is therefore the smallest possible first letter, and placing it only removes edges, so every other ready letter stays available. Repeating the argument at each position builds the smallest order letter by letter. A min-heap hands you that smallest ready letter in O(log k).

Why is a word before its own prefix invalid?

In every alphabet a word comes after its own prefix, because the comparison runs out of letters in the shorter word before it finds a difference. So cooking before cook is out of order whatever the letters are, and no rule can fix it. It is the one way a list can be impossible without any cycle among its rules.

Python

def alienOrder(words):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

words = ["tea", "ten", "ate", "act", "cat"]

Expected

"etacn"