Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 225 ยท Strings

Alien Dictionary and Lexicographic Rank of a String

Recover an unknown alphabet order from a sorted word list with topological sort, then compute the lexicographic rank of a string and the k-th permutation, with and without repeated letters.

Strings are usually compared with the alphabet we all know: a < b < c. This lesson looks at two problems where order is the whole point.

In the alien dictionary problem you are given words sorted in an unknown language, and you must reconstruct the order of its letters. It is a clean application of topological sorting hiding inside a string problem. In lexicographic rank you take a string and ask "at which position would it appear in the sorted list of all its permutations?" and, in reverse, "which permutation is at position k?". The second problem uses factorials and counting rather than generating anything, which is why it runs in polynomial time even though there are n! permutations.

Alien dictionary

The input is a list of words that is sorted lexicographically according to an alien alphabet. Example: ["wrt", "wrf", "er", "ett", "rftt"]. We do not know the alphabet, but the list tells us some facts.

Compare each adjacent pair of words. Find the first position where they differ; the two letters at that position give one rule: letter in the first word comes before letter in the second word. Only that first difference matters, because after it the words are already ordered.

  • wrt vs wrf: first difference t vs f, so t < f.
  • wrf vs er: w vs e, so w < e.
  • er vs ett: r vs t, so r < t.
  • ett vs rftt: e vs r, so e < r.

Each rule is an edge in a directed graph, and any topological order of the letters is a valid alphabet. Two special cases make the input invalid:

  • A cycle (for example a < b and b < a) means no consistent alphabet exists.
  • A longer word before its own prefix, such as ["abc", "ab"], is impossible, since a prefix always sorts first.
Python Recover the alien alphabet with Kahn's algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time is O(C) where C is the total number of characters in the input (each adjacent pair is scanned once), plus O(V + E) for the sort, with V at most the alphabet size. When several orders are valid, any one is accepted. To get a canonical answer (for example the smallest alphabet order), replace the queue with a min-heap, as in the smallest topological order.

Lexicographic rank of a string (distinct letters)

Imagine sorting all permutations of "STRING" alphabetically and numbering them from 1. What is the rank of "STRING" itself?

Do not generate the permutations. Walk through the string from left to right and ask at each position: how many permutations start with a smaller letter here, given the same prefix?

  • For position i, count the letters to the right of i that are smaller than s[i]. Call that number smaller.
  • Each smaller letter placed here lets the remaining n - i - 1 positions be arranged in (n - i - 1)! ways, all of which come before our string.
  • Add smaller * (n - i - 1)! to the rank.

At the end add 1 (ranks start at 1). With n letters the plain version takes O(n^2); a Fenwick tree counting smaller unused letters brings it to O(n log n).

With repeated letters

When letters repeat, there are fewer distinct permutations. The number of arrangements of the remaining letters is m! / (c1! * c2! * ...) where the c's are the counts of each letter still available. At each position, for every letter smaller than s[i] that is still available, pretend to place it and add the number of arrangements of what remains. Then really consume s[i].

Python Rank, and the k-th permutation back again

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

kth_permutation is the unranking direction: at each position try the letters in sorted order, subtract the size of each block of permutations you skip, and stop at the block that contains k. The cost is O(n * a) arrangement computations for an alphabet of size a. For distinct letters and no repeated work you can do it with a list of unused letters and divmod(k, (n - 1)!), the factorial number system.

Rank and unrank are the building blocks of "next permutation" (see Next Permutation) and of encoding permutations as single integers, which is handy when you need a permutation as a dictionary key or a bitmask-DP state.

Common mistakes

  • Using every pair of words in the alien dictionary instead of only adjacent pairs, or using more than the first differing letter.
  • Missing the invalid-prefix case, which makes impossible inputs look valid.
  • Dropping letters that appear in no rule; they still belong in the answer, so create graph nodes for every letter first.
  • Forgetting the +1 in the rank (ranks start at 1, but the counting gives the number of strings before).
  • Using n! when letters repeat; divide by the factorials of the counts.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the alien dictionary problem, which positions of two adjacent words give an ordering rule?

    Once the words differ at a position, their order is decided; later letters tell us nothing.
  2. 2. What does a cycle in the letter graph mean?

    A cycle such as a < b < a cannot be satisfied by any ordering.
  3. 3. What is the lexicographic rank of 'cba' among the permutations of 'abc' (1-based)?

    The sorted list is abc, acb, bac, bca, cab, cba; cba is last.
  4. 4. When a string has repeated letters, the number of arrangements of m remaining letters is:

    Dividing by c! for each letter count removes arrangements that differ only by swapping identical letters.

Summary

  • Alien dictionary: compare adjacent words, turn each first difference into an edge, then topologically sort; a cycle or a longer-word-before-its-prefix means "invalid".
  • Lexicographic rank counts, position by position, how many permutations start with a smaller letter, without generating them.
  • With repeated letters use m! / (c1! c2! ...) for each block.
  • Unranking (the k-th permutation) subtracts block sizes in sorted letter order.

Next: Pattern Matching, searching for one string inside another.