Lyndon Factorization and the Structure of Minimal Rotations

A Lyndon word is a nonempty word that is strictly smaller than every one of its proper suffixes under lexicographic order. ab is Lyndon, aba is not (its suffix a is smaller), and a is Lyndon vacuously. The class looks narrow, but it has an exact structural role: every word factors uniquely into a non-increasing sequence of Lyndon words, and that factorisation is computable in linear time with constant extra space. The same property, applied to the doubled string, decides the smallest rotation, and applied to a suffix array it defines an array that several indexing algorithms consume.

The factorisation is also the reason Lyndon words appear in compression and in enumerative combinatorics. The number of Lyndon words of length n over an alphabet of size k is

$$ \frac{1}{n} \sum_{d \mid n} \mu(d), k^{n/d} $$

where μ is the Möbius function. For binary words of length 4 that gives (16 − 4)/4 = 3, matching 0001, 0011, 0111. The formula counts equivalence classes of primitive words under rotation, which is another way of saying that Lyndon words are the canonical representatives of aperiodic necklaces.

The factorisation property

Chen, Fox, and Lyndon proved that every word w has a unique decomposition w = l₁l₂…lₘ with each lᵢ Lyndon and l₁ ≥ l₂ ≥ … ≥ lₘ. Uniqueness is what makes the decomposition a canonical form rather than one choice among many.

Two consequences follow directly. First, the last factor is the lexicographically smallest suffix of the word: if lₘ were not, some suffix would be smaller and the decomposition could be refined. Second, the sequence is non-increasing, so equal factors appear in contiguous groups; a word that is a power of a primitive root factors into copies of that root, as ababab becomes ab|ab|ab.

The decomposition coincides with the one obtained by repeatedly taking the longest Lyndon prefix of the remaining suffix. That greedy description is correct but useless as an algorithm: testing whether a prefix is Lyndon, and finding the longest one, is quadratic if done by comparing suffixes directly. Duval’s contribution is a scan that produces the same factors without testing candidates, by tracking the period of the run being examined. For banana the greedy longest Lyndon prefix is b, then an, and then an again rather than the longer ana: ana starts with a, the same character as its own proper suffix a, so it is not smaller than that suffix and is therefore not Lyndon.

Duval’s scan

Duval’s algorithm maintains three indices. i is the start of the factor currently being examined, j is the position being compared, and k tracks the position within the candidate factor that j is being compared against. The inner loop advances while the character at k is no greater than the character at j; a strictly smaller character at k resets k to i, which is how a repetition of the candidate is recognised, and an equal character advances k, which is how the period is maintained.

def duval(s):
    n, i, factors = len(s), 0, []
    while i < n:
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i            # a strictly smaller character restarts the comparison
            else:
                k += 1           # equal characters advance the period
            j += 1
        while i <= k:
            factors.append(s[i:i + j - k])
            i += j - k
    return factors

The inner while i <= k emits the factor repeatedly. When the candidate is periodic — say the scan matched anan before failing — the emitted factor is the period an, and the loop emits it as many times as the match supports. That is why ababab produces three factors rather than one: the candidate ababab is a repetition of ab, and ababab is not Lyndon, so the decomposition is the period repeated.

The loop that emits is the part usually transcribed incorrectly. j − k is the period length of the matched run, not the length of the whole match, so i advances by the period each time and the slice is the period itself. Using j − i instead produces factors that concatenate to the input but are not Lyndon and are not non-increasing, which is a failure that only shows on periodic input.

The running time is linear. Each inner-loop iteration advances j, which never moves backwards, and the position i from which the scan starts advances to at least i + 1 after each factor; the comparisons charged to a given start are therefore bounded and the total is linear in n. Extra space is three indices, which makes the algorithm usable on a streamed input provided the factors are consumed as they are emitted rather than collected.

Why the longest Lyndon prefix is a next-smaller-suffix query

Define λ[i] as the length of the longest Lyndon word starting at position i. A Lyndon word w starting at i is strictly smaller than every proper suffix of itself, and in particular smaller than w[1..], which is the prefix of the suffix starting at i+1. So a Lyndon word cannot end inside the next-smaller suffix region: before the first position j > i with s[j..] < s[i..], no suffix starting there can fail the condition, and at j the length i..j cannot be Lyndon because it is a prefix of a longer suffix (or of the whole word) and has s[j..] as a continuation that is smaller than its own remainder. The Lyndon prefix of the suffix starting at i therefore ends exactly at j, so λ[i] = j − i.

The Lyndon array therefore has the same shape as the next-smaller-value array over suffix ranks. It can be computed in O(n) from a suffix array and its inverse by a stack scan, or directly from the suffix array’s structure. This is why the array appears in algorithms that already build a suffix array: the λ values cost one linear pass on top of an index that is already there. For a text stored in a Burrows–Wheeler index, the same structure explains why runs in the last column correspond to repetitions of Lyndon factors, since a Lyndon factor’s occurrences are the contexts in which the transform produces equal predecessors.

Minimal rotation without trying every rotation

Rotating a string of length n gives n candidates, and comparing all of them costs O(n²) in the worst case if each comparison scans a long common prefix. The minimal rotation is the lexicographically smallest of them, and it can be found in linear time by discarding candidates in bulk.

Booth’s algorithm keeps two candidate start positions i and j and a matched length k. It compares s[(i+k) mod n] with s[(j+k) mod n]. If the characters are equal, k advances. If they differ, the candidate whose character is larger is discarded, and the other candidate’s start is advanced past the matched region: the loser cannot be minimal at any start within the region that was just compared, because each of those rotations agrees with the winner up to the mismatch and then loses. The discarded region can be as long as k positions, and the total work is linear because the two start indices together advance monotonically.

The discard argument is the whole content of the algorithm. A rotation starting at a position inside the matched region shares the first k characters with the winner, and its next character is the same character that lost, so it loses as well. Only positions beyond the region need consideration. This is the same amortisation that makes the prefix function linear: a monotone index plus a matched length that is consumed rather than recomputed.

Duval’s factorisation and Booth’s algorithm both run in linear time and expose the same periodic structure from different directions. The Lyndon prefix λ[i] computed at position i has length at most n, so it is a substring of the doubled string and fits inside one rotation window; the factorisation of the doubled string therefore exposes those prefixes without a suffix-array query on s itself. The factorisation costs O(n) like Booth, and it hands back the whole factor list along the way, so an algorithm that needs the factors for another purpose does not pay a second pass.

def least_rotation(s):
    n = len(s)
    i, j, k = 0, 1, 0
    while i < n and j < n and k < n:
        a, b = s[(i + k) % n], s[(j + k) % n]
        if a == b:
            k += 1
            continue
        if a > b:
            i = i + k + 1
        else:
            j = j + k + 1
        if i == j:
            j += 1
        k = 0
    return min(i, j)

Two details make the loop terminate. Advancing the loser by k+1 skips exactly the positions that the discard argument eliminates, and the i == j adjustment keeps the two candidates distinct. The bound k < n stops the comparison when a full period has matched, at which point the string is periodic and either candidate is a minimal rotation.

Generating Lyndon words in lexicographic order

The factorisation also underlies enumeration. The simplest generator maintains a current word and extends it by the smallest character until it reaches the target length n; a word that is Lyndon is emitted and then truncated, and the truncation position is found by the same suffix comparison Duval’s algorithm performs. Generating all Lyndon words of length up to n costs O(1) amortised per word, and the output size is the number of aperiodic necklaces, so the enumeration is output sensitive.

The count formula above is what makes the enumeration practical as an index: the number of Lyndon words of length exactly n grows as roughly kⁿ/n, so the set is large but its canonical representatives are exactly the objects a de Bruijn sequence construction needs. A de Bruijn sequence of order n over an alphabet of size k contains every length-n word exactly once as a cyclic substring, and one construction concatenates all Lyndon words whose length divides n in lexicographic order. The factorisation is what guarantees that each such concatenation is a single cycle rather than several.

Where the structure stops being useful

Lyndon words are defined by lexicographic order, which requires a total order on characters. For Unicode text with locale-dependent collation there is no single order, so the factorisation depends on the collation chosen and a change of collation invalidates every precomputed structure. Byte order is the only order that is stable across systems, and it is not the order a reader of the text would recognise.

The factorisation is also defined on the whole word, so it does not compose under concatenation: appending a character to a word can change factors arbitrarily far to the left. banana factors as b|an|an|a, and appending n gives b|an|an|an, which merges nothing but shifts the trailing structure. This is why an on-line application that appends to a text must either re-run Duval or maintain the factors incrementally with a stack, and the stack approach is what makes streaming factorisation possible.

Finally, the minimal-rotation problem is only meaningful for a string treated as cyclic. For a linear string the analogous question — the lexicographically smallest suffix — is answered by the suffix array’s first entry, and the Lyndon array’s relation to next-smaller suffixes is the bridge between the two. The suffix automaton answers a different question entirely, the number of distinct substrings, and does not encode rotation structure at all, which is why the two structures coexist rather than replacing one another.