On this page

Minimal Rotation, Lyndon Words & Booth's Algorithm

Why this exists

A rotation (or cyclic shift) of a string moves some letters from the front to the back: the rotations of bca are bca, cab and abc. Many things in the world are naturally cyclic: a bracelet of beads, a ring of atoms in a molecule, the outline of a shape traced around its boundary, a circular chromosome, a repeating schedule. Such an object has no natural starting point, so as a string it has equally valid spellings, one per rotation.

To store, compare or hash cyclic objects, you need one canonical spelling, the same for all rotations. The usual choice is the lexicographically minimal rotation: the rotation that comes first in dictionary order. bca, cab and abc all have canonical form abc, so two cyclic strings are equal exactly when their canonical forms are equal.

Trying all rotations and comparing them costs . This lesson shows three ways to do it in :

  1. a short two-pointer algorithm (sometimes called the "minimum expression" method), the one to write in an interview or a contest;
  2. Booth's algorithm (Kellogg Booth, 1980), which runs a KMP-style failure function over the doubled string;
  3. Duval's algorithm (Jean-Pierre Duval, 1983), which factors the string into Lyndon words, the "atoms" of string order, and reads the minimal rotation off the factorization.

Lyndon words are worth learning on their own. They are named after Roger Lyndon, who studied them in 1954; Chen, Fox and Lyndon proved in 1958 that every string splits uniquely into a non-increasing sequence of them. Today they show up in suffix sorting, in the proof of the "runs theorem" about repetitions in strings, in a bijective variant of the Burrows–Wheeler transform used in compression research, and in the fastest way to generate de Bruijn sequences.

Pattern triggers

If the problem says or has…Think of…
"lexicographically smallest rotation", "smallest cyclic shift"Two-pointer min rotation,
"necklace", "bracelet", "circular string", "ring", "the start can be anywhere"Canonical form = minimal rotation
"is a rotation of ?" occurs in (KMP / Z), or compare canonical forms
"group strings that are rotations of each other"Hash map keyed by minimal rotation
"you may move the first character to the end any number of times, smallest result"Minimal rotation (LeetCode 899 with )
"lexicographically largest suffix", "last substring in sorted order"Two-pointer max suffix, a close cousin
"factor into non-increasing Lyndon words", "smallest suffix of every prefix"Duval's algorithm
"count necklaces / bracelets with colours"Burnside's lemma (Combinatorics) and Lyndon-word counts
"shortest string containing every length- code", "de Bruijn sequence"Concatenate Lyndon words in order (Fredricksen–Maiorana)
A cyclic sequence of numbers (angles, edge lengths, chain codes) to normaliseMinimal rotation over integers; works with any total order

The meta-trigger: an object that is the same no matter where you start reading it, and you need one spelling or one comparison for it.

Intuition & first principles

Rotations, written down

For a string of length , the rotation starting at is . Equivalently, it is the length- window of starting at . That second view is the key to everything: all rotations of live side by side inside , so rotation questions become substring questions on a string of length .

For = bbaaccaadd:

rotation
0bbaaccaadd
1baaccaaddb
2aaccaaddbbsmallest
3accaaddbba
4ccaaddbbaa
5caaddbbaac
6aaddbbaaccsecond smallest
7addbbaacca
8ddbbaaccaa
9dbbaaccaad

Two rotations start with aa (at 2 and 6), and they agree on two letters before c < d decides: rotation 2 wins.

The naive method and the waste

The naive method keeps the best rotation so far and compares each new rotation with it letter by letter. Each comparison can cost up to steps, so the total is . On = aaaa…ab almost every comparison runs through a long block of as before it decides.

Here is the waste. Suppose we compare the rotations at and , they agree on letters, and then . The naive method concludes "rotation loses" and moves on. But it learned much more: for every from to , the rotation at also loses to the rotation at , because those two agree on letters and then hit the same deciding pair. So one comparison eliminates candidates at once, not one. The two-pointer algorithm is exactly "eliminate all of them, never look at them again".

An everyday analogy: two runners on a circular track

Two runners start at different points of a circular track painted with letters, reading the letters under their feet in step. As long as they read the same letters, nobody knows who started at the "better" point. The first time they read different letters, the one reading the larger letter knows that her starting point was worse, and so was every point she has passed since, because each of those is paired with an equally-far-along point of the other runner that wins the same way. So she jumps ahead past all of them and starts again. Since a runner can only jump forward and the track has starting points, the race ends after steps.

Mechanics

The two-pointer algorithm

Keep two candidate starting positions and () and a match length .

MIN-ROTATION(s):
    n = length(s);  i = 0;  j = 1;  k = 0
    while i < n and j < n and k < n:
        a = s[(i + k) mod n];  b = s[(j + k) mod n]
        if a == b:
            k += 1                       # rotations i and j agree on one more letter
        else:
            if a > b:  i = i + k + 1     # rotations i, i+1, ..., i+k all lose
            else:      j = j + k + 1     # rotations j, j+1, ..., j+k all lose
            if i == j: j += 1            # keep the two candidates different
            k = 0
    return min(i, j)

Three things can end the loop:

  • or : one pointer has run off the end, so every start except the other pointer has been eliminated. The survivor, , is the answer.
  • : rotations and are equal, so is periodic (it equals its own rotation by ). Every other start is either eliminated or equal to one of these; is the answer.
flowchart TD
    S["compare s[i+k] and s[j+k], indices mod n"] --> Q{"equal?"}
    Q -- "yes" --> K["k = k + 1"]
    K --> D{"k = n?"}
    D -- "yes: s is periodic" --> R["answer min(i, j)"]
    D -- "no" --> S
    Q -- "no" --> W{"which side is larger?"}
    W -- "s[i+k] is larger" --> I["i = i + k + 1: starts i..i+k eliminated"]
    W -- "s[j+k] is larger" --> J["j = j + k + 1: starts j..j+k eliminated"]
    I --> F["if i = j then j = j + 1, and k = 0"]
    J --> F
    F --> E{"i >= n or j >= n?"}
    E -- "yes" --> R
    E -- "no" --> S

Trace table: bbaaccaadd

Every row is one character comparison; the table was produced by a script running the code in this lesson.

Step vs ResultAction
1010b vs bequal
2011b vs a side larger; eliminated starts 0, 1
3210a vs b side larger, so
4230a vs aequal
5231a vs c side larger; eliminated 3, 4
6250a vs c side larger
7260a vs aequal
8261a vs aequal
9262c vs d side larger; eliminated 6, 7, 8
10290a vs d side larger: stop

Answer: , the rotation aaccaaddbb. Ten letter comparisons. The naive method (rung 2 below) compares 9 rotations against the best so far and reads 14 letters here; the gap is small on this string and grows to quadratic on inputs like aaa…ab.

Step 9 is the interesting one. Rotations 2 and 6 agree on aa, and then c < d. The algorithm eliminates 6, and also 7 (addbbaacca, which loses to rotation 3 accaaddbba at the same deciding pair) and 8 (ddbbaaccaa, which loses to rotation 4 ccaaddbbaa). It never reads them again.

Booth's algorithm

Booth's 1980 algorithm was the first published linear-time method. It reads the doubled string from left to right while maintaining a current best start and a KMP failure function for the string as read from . When the next letter matches what the failure function predicts, the candidate survives. When it is smaller than what was predicted, a later start beats the current one: the algorithm moves to that start, and the failure function tells it exactly how much of what it has already read is still valid, so nothing is rescanned. The amortised argument is essentially KMP's: the failure value goes up by at most one per letter read and every fallback lowers it, and Booth's paper shows the total work is linear.

def booth(s):
    """Start index of the lexicographically least rotation (Booth 1980), via a failure function on s + s."""
    n = len(s)
    if n == 0:
        return 0
    f = [-1] * (2 * n)            # failure function of the doubled string read from the candidate k
    k = 0                         # current least rotation start
    for j in range(1, 2 * n):
        i = f[j - k - 1]
        while i != -1 and s[j % n] != s[(k + i + 1) % n]:
            if s[j % n] < s[(k + i + 1) % n]:
                k = j - i - 1     # a later start wins; keep the part of the match that is still valid
            i = f[i]
        if i == -1 and s[j % n] != s[(k + i + 1) % n]:
            if s[j % n] < s[(k + i + 1) % n]:
                k = j             # the new letter itself starts a smaller rotation
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

assert booth("bbaaccaadd") == 2 and booth("banana") == 5 and booth("aaaa") == 0

The code is short but the invariants are subtle (it mixes indices relative to with absolute ones), and it is easy to break by "simplifying" it. It was checked against brute force on 20,000 random strings; it returns the smallest start of the minimal rotation, like the two-pointer method. In practice, write the two-pointer algorithm; know Booth's exists, because it is the name in the literature and in many library docs.

Lyndon words

A Lyndon word is a non-empty string that is strictly smaller than all of its other rotations. Examples:

  • a, b: a single letter has no other rotation, so it is Lyndon.
  • ab (its rotation ba is larger), aab, abb, aabab, abacb.
  • Not Lyndon: ba (rotation ab is smaller), aa (rotation aa is equal, not larger), abab (rotation by 2 is equal), aba (rotation aab is smaller).

Over the alphabet the Lyndon words of length 4 are exactly aaab, aabb and abbb.

Useful facts, each a few lines to prove:

  1. Equivalent definition. is Lyndon if and only if is strictly smaller than every proper non-empty suffix of itself. (aab < ab < b.) This is the form Duval's algorithm uses.
  2. Lyndon words are primitive: they are not a power with , since the rotation by would be equal. They are also unbordered: no proper prefix equals a suffix.
  3. Concatenation. If and are Lyndon and , then is Lyndon. (ab < b gives abb; a < ab gives aab.)
  4. Every primitive string has exactly one Lyndon rotation, namely its minimal rotation. So "classes of rotations of primitive strings" and "Lyndon words" are the same thing: a Lyndon word is the canonical name of an aperiodic necklace.

The Chen–Fox–Lyndon factorization

Theorem (Chen, Fox and Lyndon, 1958). Every non-empty string can be written uniquely as

where every is a Lyndon word and the sequence is non-increasing in lexicographic order.

Examples: banana = b · an · an · a. abbabbab = abb · abb · ab. bbaaccaadd = b · b · aaccaadd. A Lyndon word is its own factorization with .

Existence. Start with every letter as its own factor; single letters are Lyndon. While some neighbouring pair has , merge them: by fact 3 the result is Lyndon. Each merge reduces the number of factors, so this stops, and when it stops the factors are non-increasing.

Uniqueness. Suppose two factorizations differ, and look at the first factor where they differ; say is shorter than (cut off the common factors before it). Then , where is a non-empty prefix of . Now chain four facts:

  • , because is a proper suffix of the Lyndon word (fact 1);
  • , because is a prefix of ;
  • , because the factors are non-increasing;
  • , because is a prefix of .

Together , a contradiction. So the factorization is unique.

Two consequences are used constantly: is the longest Lyndon prefix of , and is the lexicographically smallest suffix of .

Duval's algorithm

Duval's algorithm computes the factorization left to right in time and extra space. It keeps three indices:

  • : where the not-yet-output part of starts;
  • : the next letter to read;
  • : the letter that is compared with.

Invariant. The part has the form where is a Lyndon word, , and is a proper (possibly empty) prefix of . The index points to the letter that would come next if the pattern continued.

Read and compare it with :

  • : the periodic pattern continues. Advance: , .
  • : the whole stretch is a single, longer Lyndon word (a larger letter "breaks the tie" in favour of the start). Set (the new is everything from ) and .
  • (or the string ends): the pattern cannot be extended. Output copies of , whose length is , and restart at the beginning of .
DUVAL(s):
    n = length(s);  i = 0;  factors = []
    while i < n:
        j = i + 1;  k = i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:  k = i       # one longer Lyndon word
            else:            k += 1      # the period continues
            j += 1
        while i <= k:                    # output the copies of w, each of length j - k
            factors.append(s[i .. i + (j - k) - 1])
            i += j - k
    return factors

Trace table: Duval on banana

Round vs CaseEffect
1010b vs astop; : output b,
2121a vs n = an, ,
2131a vs aequal,
2142n vs nequal,
2153a vs aequal,
2164end of stringstop: output an (), an (); , stop
3565end of stringstop: output a,

Result: b · an · an · a, non-increasing (b > an = an > a) and every factor is Lyndon. In round 2, after the comparison a < n, the invariant reads = an = with empty ; the three equal comparisons extend it to = anana = with = a. When the string ends, both copies of an are output and the leftover a (the ) is processed again from scratch in round 3.

For abbabbab the first round reads abb (two "greater" steps), then five "equal" steps: = abb abb ab = . At the end of the string it outputs abb, abb, and the leftover ab becomes the last factor.

Minimal rotation from Duval

Run Duval on . The minimal rotation of starts at the start of the last Lyndon factor that begins in the first half (at an index ). Intuitively, the factorization of sorts its "atoms" in non-increasing order, so the smallest atom that fits inside one full turn of the cycle is where the smallest rotation begins. In code: run Duval's outer loop on , record at the start of each round while , and return the last recorded value. On every test it returned the same (smallest) start as the two-pointer method.

Counting necklaces and Lyndon words

How many essentially different cyclic strings of length over letters are there? A necklace is a class of strings under rotation. Burnside's lemma (the number of classes equals the average number of strings fixed by a rotation; see Combinatorics) gives

where is Euler's totient function. The aperiodic necklaces correspond one-to-one with Lyndon words, and Möbius inversion gives their number:

For , : necklaces, of which are Lyndon words; for , : 6 necklaces and 3 Lyndon words (aaab, aabb, abbb, as listed above). These values were checked by enumerating all strings and taking minimal rotations. The two counts are linked by : every string is a rotation of a power of a Lyndon word.

The ladder: brute force → better → optimal

Problem: given of length , find the start of its lexicographically minimal rotation.

Rung 1: build every rotation, take the minimum

min(s[i:] + s[:i] for i in range(n)). time and extra memory per rotation built. One line; the test oracle for everything in this lesson.

Rung 2: compare in place

Keep the best start ; for each , compare rotations and letter by letter using indices modulo , without building strings. Still worst case (strings like aaa…ab), but extra memory and fast on random text, where comparisons end after a letter or two.

Rung 3: hashing or suffix structures,

With prefix hashes of , the longest common prefix of two rotations is found by binary search in , and the next letter decides the comparison. Rung 2 with comparisons gives and a small chance of error. Alternatively, build a suffix array of and take the first suffix that starts before (Suffix Arrays); this is to build, deterministic, and answers many other questions too.

Rung 4: two pointers (or Booth, or Duval),

One comparison eliminates a whole block of starts. At most about comparisons, extra memory.

RungMethodTimeExtra spaceWhy it is better
1Build all rotationsBaseline and test oracle
2Compare in place worstNo string building; fast on random text
3Hashing + binary search, or suffix array of Each comparison costs instead of
4aTwo pointersOne mismatch eliminates starts
4bBoothFailure function avoids rescanning
4cDuval on beyond Also yields the Lyndon factorization

Correctness

The two-pointer algorithm

Say a start is eliminated once we have proved that some other start gives a strictly smaller rotation.

Lemma (block elimination). If rotations and agree on their first letters and (indices mod ), then for every , rotation is strictly greater than rotation .

Proof. Rotation begins with , then ; rotation begins with , then . The first letters are equal (part of the agreement), and the next letter is larger on the side. So rotation is strictly greater. ∎

Invariant. At the top of the loop, every start in other than and is eliminated.

Initially , , and the range contains only . When jumps to , the lemma eliminates . Starts below the old were already handled, the new block covers everything from the old up to the new , and anything between the new and (if is further right) was below the old maximum. If the new lands on , the extra j += 1 keeps the pointers distinct; 's old position is now , so nothing is lost. The case where jumps is symmetric.

At the end, either one pointer is , so every start except the other pointer is eliminated and the other pointer is the minimal rotation; or , so rotations and are equal and is invariant under rotation by . In the second case every start gives the same rotation as , which is smaller, so by repeating the argument it is either eliminated or equal to rotation . Either way is a start of the minimal rotation, and because every smaller start was eliminated (strictly larger), it is the smallest such start.

Termination and time. Each mismatch increases by (plus possibly 1), paying for the equal comparisons before it and itself. Since and stay below while the loop runs, , so all mismatches together pay for fewer than comparisons. The final run of equal comparisons, if reaches , adds at most . Total at most about comparisons. On a script's exhaustive search over all 4,096 binary strings of length 12, the maximum was 30 comparisons; on copies of a it is 1,000.

Duval's algorithm

We give the proof sketch from Duval (1983) and cp-algorithms.

Lemma. If is Lyndon, is a proper prefix of , and is a letter larger than the letter that follows in , then is Lyndon for every .

Idea. Any proper suffix of starts inside some copy of or inside . Line it up against the start of the whole string: it agrees with the periodic continuation until it reaches the final letter , which is larger than what the period predicts, or until a letter where it is larger because is Lyndon. Either way the suffix is strictly larger, so by fact 1 the word is Lyndon.

With the lemma, the three cases maintain the invariant " with Lyndon": the equal case extends (wrapping into a new copy of when becomes all of ); the greater case turns everything into a single new Lyndon word by the lemma; and in the smaller case, the copies of are exactly the next factors of the CFL factorization. Why may they be output? Any Lyndon word starting at and extending past would have as a prefix with smaller than the period predicts, which makes a later suffix smaller than the word itself, impossible for a Lyndon word. So the longest Lyndon prefix of is , which is the next factor, and repeating the argument gives copies.

Time. In each round, the inner loop advances from , and the round outputs at least letters and then moves past them, leaving the part (shorter than the amount output) to be read again. So the letters re-read are bounded by the letters output, and the total number of comparisons is at most about (cp-algorithms states the same bound). Linear time, constant extra space.

Complexity

AlgorithmTimeExtra spaceNotes
Naive (rung 1/2) worst / Near-linear on random text
Hashing + binary searchMonte Carlo
Suffix array of (or with SA-IS)Answers much more than the minimum
Two pointers, about comparisonsInterview / contest default
BoothFailure function of length
Duval factorization, about comparisons (output aside)Online in a weak sense: outputs factors left to right
Duval on for min rotation for , or index mod Gives the same start as two pointers

Best case for the two-pointer method is about comparisons (for example when the first letter is the unique smallest one: every other start loses on its first letter). All of these methods use only comparisons between letters, so they work for any totally ordered alphabet: integers, angles, tuples.

Implementation

Minimal rotation (two pointers)

Each version asserts the trace above, a few edge cases (empty string, one letter, all-equal letters, periodic strings) and then checks against the brute force of rung 1 on 20,000 random strings over alphabets of size 1–3, including that the returned start is the smallest start of the minimal rotation.

import random


def min_rotation(s):
    """Smallest index i such that s[i:] + s[:i] is the lexicographically least rotation."""
    n = len(s)
    if n == 0:
        return 0
    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 += k + 1          # starts i..i+k lose to j..j+k
        else:
            j += k + 1          # starts j..j+k lose to i..i+k
        if i == j:
            j += 1
        k = 0
    return min(i, j)


def canonical(s):
    i = min_rotation(s)
    return s[i:] + s[:i]


def brute(s):
    n = len(s)
    return min(range(n), key=lambda i: (s[i:] + s[:i], i)) if n else 0


if __name__ == "__main__":
    assert min_rotation("bbaaccaadd") == 2 and canonical("bbaaccaadd") == "aaccaaddbb"
    assert min_rotation("banana") == 5 and min_rotation("abab") == 0
    assert min_rotation("") == 0 and min_rotation("z") == 0 and min_rotation("aaaa") == 0
    assert canonical("cab") == canonical("bca") == "abc"
    rng = random.Random(1)
    for _ in range(20000):
        s = "".join(rng.choice("abc"[:rng.randint(1, 3)]) for _ in range(rng.randint(0, 12)))
        assert min_rotation(s) == brute(s), s
    print("ok")
import java.util.Random;

public class MinRotation {
    /** Smallest index i such that rotating s to start at i gives the lexicographically least rotation. */
    static int minRotation(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int i = 0, j = 1, k = 0;
        while (i < n && j < n && k < n) {
            char a = s.charAt((i + k) % n), b = s.charAt((j + k) % n);
            if (a == b) { k++; continue; }
            if (a > b) i += k + 1; else j += k + 1;
            if (i == j) j++;
            k = 0;
        }
        return Math.min(i, j);
    }

    static String rotate(String s, int i) { return s.substring(i) + s.substring(0, i); }

    static int brute(String s) {
        int best = 0;
        for (int i = 1; i < s.length(); i++) if (rotate(s, i).compareTo(rotate(s, best)) < 0) best = i;
        return best;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        check(minRotation("bbaaccaadd") == 2 && rotate("bbaaccaadd", 2).equals("aaccaaddbb"), "trace");
        check(minRotation("banana") == 5 && minRotation("abab") == 0, "small");
        check(minRotation("") == 0 && minRotation("z") == 0 && minRotation("aaaa") == 0, "edge");
        Random rng = new Random(1);
        for (int it = 0; it < 20000; it++) {
            int sigma = 1 + rng.nextInt(3), n = rng.nextInt(13);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append((char) ('a' + rng.nextInt(sigma)));
            String s = sb.toString();
            check(minRotation(s) == brute(s), s);
        }
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <string>

// Smallest index i such that rotating s to start at i gives the lexicographically least rotation.
int minRotation(const std::string& s) {
    int n = static_cast<int>(s.size());
    if (n == 0) return 0;
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        char a = s[(i + k) % n], b = s[(j + k) % n];
        if (a == b) { ++k; continue; }
        if (a > b) i += k + 1; else j += k + 1;
        if (i == j) ++j;
        k = 0;
    }
    return std::min(i, j);
}

std::string rotate(const std::string& s, int i) { return s.substr(i) + s.substr(0, i); }

int brute(const std::string& s) {
    int best = 0;
    for (int i = 1; i < static_cast<int>(s.size()); ++i)
        if (rotate(s, i) < rotate(s, best)) best = i;
    return best;
}

int main() {
    assert(minRotation("bbaaccaadd") == 2 && rotate("bbaaccaadd", 2) == "aaccaaddbb");
    assert(minRotation("banana") == 5 && minRotation("abab") == 0);
    assert(minRotation("") == 0 && minRotation("z") == 0 && minRotation("aaaa") == 0);
    std::mt19937 rng(1);
    for (int it = 0; it < 20000; ++it) {
        int sigma = 1 + rng() % 3, n = rng() % 13;
        std::string s;
        for (int i = 0; i < n; ++i) s += static_cast<char>('a' + rng() % sigma);
        assert(minRotation(s) == brute(s));
    }
    std::cout << "ok\n";
    return 0;
}
/** Smallest index i such that rotating s to start at i gives the lexicographically least rotation. */
export function minRotation(s: string): number {
  const n = s.length;
  if (n === 0) return 0;
  let i = 0;
  let j = 1;
  let k = 0;
  while (i < n && j < n && k < n) {
    const a = s[(i + k) % n];
    const b = s[(j + k) % n];
    if (a === b) {
      k++;
      continue;
    }
    if (a > b) i += k + 1;
    else j += k + 1;
    if (i === j) j++;
    k = 0;
  }
  return Math.min(i, j);
}

const rotate = (s: string, i: number): string => s.slice(i) + s.slice(0, i);

function brute(s: string): number {
  let best = 0;
  for (let i = 1; i < s.length; i++) if (rotate(s, i) < rotate(s, best)) best = i;
  return best;
}

if (minRotation("bbaaccaadd") !== 2 || rotate("bbaaccaadd", 2) !== "aaccaaddbb") throw new Error("trace");
if (minRotation("banana") !== 5 || minRotation("abab") !== 0) throw new Error("small");
if (minRotation("") !== 0 || minRotation("z") !== 0 || minRotation("aaaa") !== 0) throw new Error("edge");
for (let it = 0; it < 20000; it++) {
  const sigma = 1 + Math.floor(Math.random() * 3);
  const n = Math.floor(Math.random() * 13);
  let s = "";
  for (let i = 0; i < n; i++) s += "abc"[Math.floor(Math.random() * sigma)];
  if (minRotation(s) !== brute(s)) throw new Error(s);
}
console.log("ok");

Lyndon factorization (Duval) and minimal rotation from it

Each version asserts the factorizations from this lesson, then checks on 20,000 random strings that the factors concatenate back to , that every factor is a Lyndon word (by brute force over its rotations), that the factors are non-increasing, and that the Duval-based minimal rotation agrees with brute force.

import random


def duval(s):
    """Chen-Fox-Lyndon factorization: Lyndon words w1 >= w2 >= ... whose concatenation is s."""
    n, i, factors = len(s), 0, []
    while i < n:
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            k = i if s[k] < s[j] else k + 1
            j += 1
        while i <= k:                       # output the copies of the period, each of length j - k
            factors.append(s[i:i + j - k])
            i += j - k
    return factors


def min_rotation_duval(s):
    """Start of the least rotation = start of the last Lyndon factor of s + s that begins before n."""
    n, t, i, ans = len(s), s + s, 0, 0
    while i < n:
        ans = i
        j, k = i + 1, i
        while j < 2 * n and t[k] <= t[j]:
            k = i if t[k] < t[j] else k + 1
            j += 1
        while i <= k:
            i += j - k
    return ans


def is_lyndon(w):
    return len(w) > 0 and all(w < w[r:] + w[:r] for r in range(1, len(w)))


if __name__ == "__main__":
    assert duval("banana") == ["b", "an", "an", "a"]
    assert duval("abbabbab") == ["abb", "abb", "ab"]
    assert duval("bbaaccaadd") == ["b", "b", "aaccaadd"] and duval("") == []
    assert min_rotation_duval("bbaaccaadd") == 2 and min_rotation_duval("banana") == 5
    rng = random.Random(1)
    for _ in range(20000):
        s = "".join(rng.choice("abc"[:rng.randint(1, 3)]) for _ in range(rng.randint(0, 12)))
        f = duval(s)
        assert "".join(f) == s and all(map(is_lyndon, f))
        assert all(f[x] >= f[x + 1] for x in range(len(f) - 1))
        best = min(range(len(s)), key=lambda i: (s[i:] + s[:i], i)) if s else 0
        assert min_rotation_duval(s) == best, s
    print("ok")
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Duval {
    /** Chen-Fox-Lyndon factorization: Lyndon words w1 >= w2 >= ... whose concatenation is s. */
    static List<String> duval(String s) {
        int n = s.length(), i = 0;
        List<String> factors = new ArrayList<>();
        while (i < n) {
            int j = i + 1, k = i;
            while (j < n && s.charAt(k) <= s.charAt(j)) {
                k = s.charAt(k) < s.charAt(j) ? i : k + 1;
                j++;
            }
            while (i <= k) { factors.add(s.substring(i, i + j - k)); i += j - k; }
        }
        return factors;
    }

    /** Start of the least rotation = start of the last Lyndon factor of s + s that begins before n. */
    static int minRotationDuval(String s) {
        int n = s.length(), i = 0, ans = 0;
        String t = s + s;
        while (i < n) {
            ans = i;
            int j = i + 1, k = i;
            while (j < 2 * n && t.charAt(k) <= t.charAt(j)) {
                k = t.charAt(k) < t.charAt(j) ? i : k + 1;
                j++;
            }
            while (i <= k) i += j - k;
        }
        return ans;
    }

    static String rotate(String s, int r) { return s.substring(r) + s.substring(0, r); }

    static boolean isLyndon(String w) {
        if (w.isEmpty()) return false;
        for (int r = 1; r < w.length(); r++) if (w.compareTo(rotate(w, r)) >= 0) return false;
        return true;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        check(duval("banana").equals(List.of("b", "an", "an", "a")), "banana");
        check(duval("abbabbab").equals(List.of("abb", "abb", "ab")), "abbabbab");
        check(duval("").isEmpty() && minRotationDuval("bbaaccaadd") == 2, "edge");
        Random rng = new Random(1);
        for (int it = 0; it < 20000; it++) {
            int sigma = 1 + rng.nextInt(3), n = rng.nextInt(13);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) sb.append((char) ('a' + rng.nextInt(sigma)));
            String s = sb.toString();
            List<String> f = duval(s);
            check(String.join("", f).equals(s), "concat " + s);
            for (int x = 0; x < f.size(); x++) {
                check(isLyndon(f.get(x)), "lyndon " + s);
                if (x + 1 < f.size()) check(f.get(x).compareTo(f.get(x + 1)) >= 0, "order " + s);
            }
            int best = 0;
            for (int r = 1; r < n; r++) if (rotate(s, r).compareTo(rotate(s, best)) < 0) best = r;
            check(minRotationDuval(s) == best, "rotation " + s);
        }
        System.out.println("ok");
    }
}
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <vector>

// Chen-Fox-Lyndon factorization: Lyndon words w1 >= w2 >= ... whose concatenation is s.
std::vector<std::string> duval(const std::string& s) {
    int n = static_cast<int>(s.size()), i = 0;
    std::vector<std::string> factors;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            k = s[k] < s[j] ? i : k + 1;
            ++j;
        }
        while (i <= k) { factors.push_back(s.substr(i, j - k)); i += j - k; }
    }
    return factors;
}

// Start of the least rotation = start of the last Lyndon factor of s + s that begins before n.
int minRotationDuval(const std::string& s) {
    int n = static_cast<int>(s.size()), i = 0, ans = 0;
    std::string t = s + s;
    while (i < n) {
        ans = i;
        int j = i + 1, k = i;
        while (j < 2 * n && t[k] <= t[j]) {
            k = t[k] < t[j] ? i : k + 1;
            ++j;
        }
        while (i <= k) i += j - k;
    }
    return ans;
}

std::string rotate(const std::string& s, int r) { return s.substr(r) + s.substr(0, r); }

bool isLyndon(const std::string& w) {
    if (w.empty()) return false;
    for (int r = 1; r < static_cast<int>(w.size()); ++r) if (!(w < rotate(w, r))) return false;
    return true;
}

int main() {
    assert((duval("banana") == std::vector<std::string>{"b", "an", "an", "a"}));
    assert((duval("abbabbab") == std::vector<std::string>{"abb", "abb", "ab"}));
    assert(duval("").empty() && minRotationDuval("bbaaccaadd") == 2);
    std::mt19937 rng(1);
    for (int it = 0; it < 20000; ++it) {
        int sigma = 1 + rng() % 3, n = rng() % 13;
        std::string s;
        for (int i = 0; i < n; ++i) s += static_cast<char>('a' + rng() % sigma);
        std::vector<std::string> f = duval(s);
        std::string joined;
        for (std::size_t x = 0; x < f.size(); ++x) {
            joined += f[x];
            assert(isLyndon(f[x]));
            if (x + 1 < f.size()) assert(f[x] >= f[x + 1]);
        }
        assert(joined == s);
        int best = 0;
        for (int r = 1; r < n; ++r) if (rotate(s, r) < rotate(s, best)) best = r;
        assert(minRotationDuval(s) == best);
    }
    std::cout << "ok\n";
    return 0;
}
/** Chen-Fox-Lyndon factorization: Lyndon words w1 >= w2 >= ... whose concatenation is s. */
export function duval(s: string): string[] {
  const n = s.length;
  const factors: string[] = [];
  let i = 0;
  while (i < n) {
    let j = i + 1;
    let k = i;
    while (j < n && s[k] <= s[j]) {
      k = s[k] < s[j] ? i : k + 1;
      j++;
    }
    while (i <= k) {
      factors.push(s.slice(i, i + j - k));
      i += j - k;
    }
  }
  return factors;
}

/** Start of the least rotation = start of the last Lyndon factor of s + s that begins before n. */
export function minRotationDuval(s: string): number {
  const n = s.length;
  const t = s + s;
  let i = 0;
  let ans = 0;
  while (i < n) {
    ans = i;
    let j = i + 1;
    let k = i;
    while (j < 2 * n && t[k] <= t[j]) {
      k = t[k] < t[j] ? i : k + 1;
      j++;
    }
    while (i <= k) i += j - k;
  }
  return ans;
}

const rotate = (s: string, r: number): string => s.slice(r) + s.slice(0, r);
const isLyndon = (w: string): boolean => w.length > 0 && [...Array(w.length).keys()].slice(1).every((r) => w < rotate(w, r));
const same = (a: string[], b: string[]): boolean => a.length === b.length && a.every((x, i) => x === b[i]);

if (!same(duval("banana"), ["b", "an", "an", "a"])) throw new Error("banana");
if (!same(duval("abbabbab"), ["abb", "abb", "ab"])) throw new Error("abbabbab");
if (duval("").length !== 0 || minRotationDuval("bbaaccaadd") !== 2) throw new Error("edge");
for (let it = 0; it < 20000; it++) {
  const sigma = 1 + Math.floor(Math.random() * 3);
  const n = Math.floor(Math.random() * 13);
  let s = "";
  for (let i = 0; i < n; i++) s += "abc"[Math.floor(Math.random() * sigma)];
  const f = duval(s);
  if (f.join("") !== s || !f.every(isLyndon)) throw new Error("factors " + s);
  for (let x = 0; x + 1 < f.length; x++) if (f[x] < f[x + 1]) throw new Error("order " + s);
  let best = 0;
  for (let r = 1; r < n; r++) if (rotate(s, r) < rotate(s, best)) best = r;
  if (minRotationDuval(s) !== best) throw new Error("rotation " + s);
}
console.log("ok");

Language notes. All four compare characters by code unit, which is a valid total order; for user text, decide whether you want code-point order or a locale collation before canonicalising, and normalise Unicode first (Strings in Depth). For integer sequences (angles, edge lengths), replace the string with an array; nothing else changes. The modulo in the two-pointer loop can be avoided by indexing a doubled array, at the cost of memory.

Applications

Canonical forms of cyclic strings and necklaces

Store each cyclic object by its minimal rotation, and equality, hashing and sorting all just work. Typical uses:

  • Grouping rotations. "Group the strings that are rotations of each other" becomes a hash map from canonical form to list. per string instead of .
  • Shape matching in image processing. A boundary traced as a Freeman chain code (a sequence of direction codes 0–7) depends on where tracing started. The standard normalisation treats the code as circular and picks the starting point that makes it the smallest sequence, which is the minimal rotation; taking first differences of the code first also makes it rotation-invariant for the shape (Gonzalez and Woods, Digital Image Processing, chain codes).
  • Canonical labels for cycles in graphs and molecules. Canonical labelling of a ring (in a chemical structure, or a cycle in a planar graph's embedding) needs a starting atom and a direction. A common building block is "minimal rotation of the label sequence, in both directions, take the smaller" (which handles reflections too). Full canonical labelling of molecules or graphs needs much more than this (for example, canonical SMILES generation or the nauty tool), but for purely cyclic pieces it is the core step. Shiloach's 1981 paper "Fast canonization of circular strings" is named after exactly this task.
  • Circular genomes. Bacterial plasmids and mitochondrial DNA are circular, so the same sequence can be reported from different starting points. One simple way to get a canonical form for deduplication is the minimal rotation, taken over the sequence and its reverse complement.

Circular string matching

  • Is a rotation of ? Equal lengths and occurs in (KMP or Z, ). Or compare canonical forms, also , and the canonical form can be stored and indexed.
  • Does any rotation of a pattern occur in a text ? Build an automaton for all rotations of (Aho–Corasick on patterns is to build), or slide a window over and compare canonical forms (too slow naively), or use a suffix automaton of (Suffix Automaton) and walk through it, keeping matches of length at least : .

Lyndon words in modern string algorithms

  • Bijective Burrows–Wheeler transform. The standard BWT (the transform inside bzip2) needs an end marker or an extra index to be inverted. Joseph Gil and David Scott's bijective variant sorts the rotations of the Lyndon factors of the input instead, which makes the transform a bijection on strings; Manfred Kufleitner (2009) analysed it. It is a research and enthusiast topic rather than a mainstream format, but it is a clean example of the factorization at work. The BWT itself is covered with compression in Real-World Compression.
  • Suffix sorting. The suffix array of a string can be built from its Lyndon factorization (for example Uwe Baier's 2016 algorithm "Linear-time suffix sorting — a new approach for suffix array construction"), because the factorization tells you a lot about the order of suffixes in advance.
  • The runs theorem. Bannai, I, Inenaga, Nakashima, Takeda and Tsuruta (2017) proved that a string of length has fewer than maximal repetitions ("runs"), settling a conjecture of Kolpakov and Kucherov, using Lyndon roots: each run contains a Lyndon word with respect to one of two opposite orders.
  • De Bruijn sequences. A de Bruijn sequence of order over letters is a cyclic string of length that contains every length- string exactly once as a window. Concatenating, in lexicographic order, all Lyndon words whose length divides gives the lexicographically smallest one (Fredricksen and Maiorana, 1978). Duval also gave a simple algorithm that lists Lyndon words in order with constant amortised time per word. The "crack the safe" problem in the practice ladder is exactly this construction.

Pitfalls & edge cases

  • Strict versus non-strict. Lyndon means strictly smaller than every other rotation. aa is not Lyndon; its factorization is a · a. The Duval condition is s[k] <= s[j] (not <), so that equal letters extend the period.
  • Which index on ties. For periodic strings like abab, several starts give the minimal rotation. The algorithms in this lesson return the smallest; if a problem wants a different one (for example "the latest"), adjust and test.
  • The i == j bump. Forgetting if i == j: j += 1 makes both candidates equal and the loop compares a rotation with itself until , returning a wrong answer for strings like baa.
  • k < n guard. Without it, an all-equal string loops forever (or reads out of bounds without the modulo).
  • Empty string. Return 0 (or handle separately); is already out of range when or .
  • Modulo cost. The % in the hot loop is slow in some languages. Double the string or use if x >= n: x -= n.
  • Booth edits. Booth's code mixes relative and absolute indices; "cleaning it up" is a classic way to break it. Test any change against brute force.
  • Bracelets need reflections too. A bracelet (a necklace you can also flip over) needs the minimum of the minimal rotation of and of .
  • Comparing with a locale. Lexicographic order by code unit is not dictionary order for humans (uppercase before lowercase, accents). For canonical forms that is fine; for display it is not.

Variations

  • Maximal rotation: flip the comparison (or negate integer values).
  • Lexicographically largest suffix (LeetCode 1163): a two-pointer method of the same shape, but the candidates are suffixes, not rotations, so matches stop at the end of the string instead of wrapping.
  • Smallest suffix of every prefix: the last Lyndon factor of each prefix; Duval's algorithm can report it for all prefixes in total.
  • Minimal rotation of a sequence with a different order: any total order on letters works, for example comparing tuples, or a custom alphabet order.
  • Minimum over rotations and reflections: run the algorithm on and on .
  • Generalised Lyndon words and infinite orders: there are versions for alternating order (used for the runs theorem) and for infinite words.
  • Counting necklaces with constraints (fixed content, forbidden patterns): Burnside or Pólya with a DP inside; see Combinatorics.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Rotate String (LeetCode 796) — Decide whether one string is a rotation of another. Teaches the trick and canonical forms.

Hint

Equal lengths and goal in s + s; or compare canonical(s) == canonical(goal).

2. Repeated Substring Pattern (LeetCode 459) — Is the string a block repeated at least twice? Teaches the link between rotations and periodicity.

Hint

is a repetition exactly when it equals one of its non-trivial rotations, that is, when occurs in (s + s)[1:-1].

3. Minimal Rotation (CSES 1110) — Print the lexicographically smallest rotation of a string of up to letters. Teaches the algorithm under a real limit.

Solution
import sys

def main():
    s = sys.stdin.readline().strip()
    i = min_rotation(s)              # two-pointer version from the implementation
    sys.stdout.write(s[i:] + s[:i] + "\n")

. In Python, letters take on the order of a second with the pure loop.

4. Orderly Queue (LeetCode 899) — You may repeatedly move one of the first letters to the end; find the smallest reachable string. Teaches that is exactly minimal rotation, and allows any permutation.

Solution
def orderly_queue(s, k):
    if k == 1:
        i = min_rotation(s)
        return s[i:] + s[:i]
    return "".join(sorted(s))        # with two movable letters, adjacent swaps are possible

assert orderly_queue("cba", 1) == "acb" and orderly_queue("baaca", 3) == "aaabc"

With , you can rotate the string so that any adjacent pair sits at the front and swap them, so every permutation is reachable; the smallest is the sorted one.

5. Lexicographically Smallest String After Applying Operations (LeetCode 1625) — Digits can be rotated by a fixed amount and odd positions can have a fixed number added mod 10; find the smallest result. Teaches enumerating the reachable states, a cousin of canonical forms.

Hint

The state space is small (at most states). BFS over states, or enumerate the reachable rotation offsets (a subgroup generated by ) and the reachable additions independently for odd and even positions.

6. Secret Combination (Codeforces 496B) — A lock shows digits; one button adds 1 to every digit mod 10, the other rotates the digits by one. Print the smallest number reachable. Teaches combining a small "add" dimension with minimal rotation.

Solution

Try each of the 10 additions; for each resulting string take the minimal rotation; return the smallest of the 10 candidates. .

def secret_combination(digits):
    best = None
    for add in range(10):
        t = "".join(str((int(c) + add) % 10) for c in digits)
        i = min_rotation(t)
        cand = t[i:] + t[:i]
        best = cand if best is None or cand < best else best
    return best

assert secret_combination("579") == "024" and secret_combination("2014") == "0142"

7. Last Substring in Lexicographical Order (LeetCode 1163) — Return the lexicographically largest substring (always a suffix). Teaches the two-pointer elimination on suffixes instead of rotations.

Solution
def last_substring(s):
    i, j, k, n = 0, 1, 0, len(s)
    while j + k < n:
        if s[i + k] == s[j + k]:
            k += 1
        elif s[i + k] > s[j + k]:
            j += k + 1               # suffixes j..j+k lose
            k = 0
        else:
            i = max(i + k + 1, j)    # suffixes i..i+k lose
            j, k = i + 1, 0
    return s[i:]

assert last_substring("abab") == "bab" and last_substring("leetcode") == "tcode"

The same block-elimination lemma applies, with the twist that when a suffix runs out first, it is a prefix of the other and therefore smaller; the loop condition j + k < n handles that. Checked against max(s[i:] for i in range(n)) on 20,000 random strings.

8. Counting Necklaces (CSES 2209) — Count the necklaces of beads with colours, modulo . Teaches Burnside's lemma for rotations.

Hint

, which is the -formula above grouped by . Divide using a modular inverse of . The full derivation belongs to Combinatorics.

9. Cracking the Safe (LeetCode 753) — Build the shortest string that contains every -digit code over digits as a substring. Teaches de Bruijn sequences from Lyndon words.

Solution

Generate the Lyndon words over of length at most in lexicographic order (Duval's generation algorithm), concatenate those whose length divides , and append the first symbols of the cycle to "unroll" it. Length , the minimum possible.

def lyndon_words(k, n):
    """All Lyndon words over 0..k-1 of length <= n, in lexicographic order (Duval 1988)."""
    w = [-1]
    while w:
        w[-1] += 1
        yield w
        m = len(w)
        while len(w) < n:
            w.append(w[len(w) - m])      # extend periodically
        while w and w[-1] == k - 1:
            w.pop()                      # drop maximal letters, then increment

def crack_safe(n, k):
    seq = [d for w in lyndon_words(k, n) if n % len(w) == 0 for d in w]
    tail = [seq[i % len(seq)] for i in range(n - 1)]   # unroll the cycle (seq is short when k = 1)
    return "".join(map(str, seq + tail))

assert crack_safe(3, 2) == "0001011100"
s = crack_safe(2, 3)
assert len(s) == 3 ** 2 + 1 and len({s[i:i + 2] for i in range(len(s) - 1)}) == 9

The cyclic sequence for , is 00010111 (from 0, 001, 011, 1); every 3-bit code appears exactly once as a cyclic window.

Common mistakes & interview follow-ups

"Why does one mismatch eliminate starts?" Because each start is paired with , which agrees with it on letters and then wins at the same deciding pair.

"Why is it linear?" Each mismatch moves a pointer forward by , paying for the matches before it; pointers never move back and stop at . At most about comparisons.

"Is a rotation of ?" Same length and in . Follow-up: "now do it for a million strings": canonical forms in a hash set.

"What is a Lyndon word, and why care?" Strictly smaller than all its rotations. Every string factors uniquely into non-increasing Lyndon words; the last factor is the smallest suffix; the minimal rotation of a primitive string is a Lyndon word.

"Necklaces versus bracelets?" Rotations only, versus rotations and reflections. Canonical bracelet: the smaller of the canonical forms of and .

Mistakes interviewers watch for: forgetting the i == j bump; using < instead of <= in Duval; returning the rotation when the index was asked for (or the reverse); building all rotations "just to check" and calling it linear; mishandling the empty string.

Quick quiz

1. What is the Lyndon factorization of abaab?

Answer

ab · aab. Both are Lyndon, and ab > aab (they differ at the second letter, b > a). Duval's first round compares / = a/b (greater: = ab), then / = a/a (equal: the period continues), then / = b/a (smaller: stop). It outputs ab and restarts at index 2, where a/a (equal) and then a/b (greater) read aab as one Lyndon word before the string ends.

2. Run the two-pointer algorithm on cab by hand. How many comparisons?

Answer

: c vs a, the side is larger, so , which equals , so . Then : a vs b, the side is larger, so : stop. Answer 1 (abc), after 2 comparisons.

3. Which of aab, aba, abab, abb, b are Lyndon words?

Answer

aab, abb and b. aba has the smaller rotation aab; abab equals its rotation by 2.

4. How many binary necklaces of length 6 are there, and how many of them are Lyndon words?

Answer

14 necklaces; 9 Lyndon words. The other 5 are periodic: 000000, 111111, 010101, 001001, 011011.

5. Why is the last factor of the Lyndon factorization the smallest suffix of the string?

Answer

Any suffix starts inside some factor . A proper suffix of is larger than (Lyndon), and ; a suffix starting exactly at begins with , and when it is longer than , so it is larger. So nothing is smaller than itself.

Further reading / sources

  • Kellogg S. Booth, "Lexicographically least circular substrings", Information Processing Letters 10(4–5), 1980.
  • Yossi Shiloach, "Fast canonization of circular strings", Journal of Algorithms 2(2), 1981.
  • K. T. Chen, R. H. Fox, R. C. Lyndon, "Free differential calculus IV. The quotient groups of the lower central series", Annals of Mathematics 68, 1958 (the factorization theorem).
  • Jean-Pierre Duval, "Factorizing words over an ordered alphabet", Journal of Algorithms 4(4), 1983; and "Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée", Theoretical Computer Science 60, 1988 (generating Lyndon words).
  • M. Lothaire, Combinatorics on Words, Cambridge University Press, 1997, chapter 5 (Lyndon words).
  • Harold Fredricksen, James Maiorana, "Necklaces of beads in k colors and k-ary de Bruijn sequences", Discrete Mathematics 23(3), 1978.
  • Joseph Yossi Gil, David Allen Scott, "A bijective string sorting transform", arXiv:1201.3077, 2012; Manfred Kufleitner, "On bijective variants of the Burrows–Wheeler transform", Prague Stringology Conference 2009.
  • Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, "The 'Runs' Theorem", SIAM Journal on Computing 46(5), 2017.
  • Uwe Baier, "Linear-time suffix sorting — a new approach for suffix array construction", CPM 2016.
  • cp-algorithms: Lyndon factorization (Duval's algorithm, its complexity, and the minimal cyclic shift).

Previous lesson: Palindromes & Manacher's Algorithm · Next lesson: How Regex Engines Work

Related: String Algorithms overview · KMP & the Prefix Function · The Z-Algorithm · String Hashing in Depth · Two Pointers · Strings in Depth · Course home