Lyndon words and minimal rotation

Why this matters when you build with AI

Ask an AI tool for "the smallest rotation of a string" and it will often return this: build all n rotations, sort them, return the first. That is correct, but it stores n strings of length n, so it needs O(n^2) memory and time. For n = 200000 that is about 4 * 10^10 characters, which does not fit. A tool may also return a version that compares rotations by index and gets the tie cases wrong, or that reads past the end of the doubled string.

You can catch these in a few minutes. Write the brute force that compares all rotations, since it is slow and obviously right. Then compare the fast version with it on every short string over a small alphabet. This lesson builds that habit with the method called Duval's factorisation, which is the basis of the fast rotation method.

A prompt that states the limits and asks for the check:

Write a C++17 function that returns the start index of the lexicographically smallest
rotation of a string s, where 1 <= |s| <= 200000 and the letters are lowercase.
Use O(|s|) time and O(|s|) memory. Do not build all rotations.
Say which index you return when two rotations are equal, and explain why.

A good answer uses one pass over the string doubled, runs in O(n) time, and says which index it returns when the string is periodic, such as abab, where two rotations are equal. Check each of those by reading the code, then run it against the brute force on every short string (section "Check against a brute force" below).

Terms used

A rotation (also called a cyclic shift) of a string moves some prefix to the end. The rotations of abc are abc, bca and cab.
Lexicographic order is dictionary order. Compare the first position where two strings differ. If one string is a prefix of the other, the shorter one is smaller. So aab is smaller than ab, and ab is not smaller than aab.
A suffix is a tail of a string, such as bab in abab. A proper suffix is any suffix except the whole string.
A Lyndon word is a nonempty string that is strictly smaller than each of its proper suffixes. The first Lyndon words over a and b are a, b, ab, aab and abb. The string abab is not one, because its suffix ab is a prefix of it, so abab is larger.
A factorisation of a string is a way to cut it into pieces, here Lyndon words, so that the pieces written in order give back the string.
O(...) means the work grows no faster than the given expression as the input grows.

The idea: Lyndon words are the smallest pieces

The rule for a Lyndon word is strict. The word aab is smaller than its suffixes ab and b, because aa is smaller than ab and a is smaller than b. So aab is a Lyndon word. The word aba is not. Its suffix a is a prefix of aba, so aba is larger than that suffix.

Lyndon words are useful because every string can be cut into Lyndon words in one canonical way. The pieces are non-increasing in dictionary order. Here is the example used throughout the lesson:

abcdba = abcdb + a

The piece abcdb is a Lyndon word: each of its suffixes bcdb, cdb, db and b is larger than abcdb. The piece a is also Lyndon. The pieces are in order abcdb >= a, so the cut is a valid factorisation.

Duval's factorisation

The rule

The algorithm walks through the string once, and keeps a current start i and two scan positions j and k. The string from i to j - 1 is a repeated block: it is the Lyndon word w repeated, followed by a prefix of w. The position k marks where the period restarts, so the period length is j - k.

For each step, compare the character at k with the character at j:

If s[k] < s[j], the current block extends to a bigger Lyndon word. Set k = i, so the whole block from i is now the one period.
If s[k] == s[j], the block continues to repeat. Move k forward by one.
If s[k] > s[j], the block cannot grow into a Lyndon word. Stop scanning.

When the scan stops, output copies of the period (length j - k) starting at i, for as long as i <= k. Then move on to the rest of the string.

A trace on abcdba

The Python program in section "Trace in Python" prints the scan for each outer round. Here is what it shows:

round 1: i = 0, scan stops at j = 6, k = 1, period = 5, factor abcdb
round 2: i = 5, scan stops at j = 6, k = 5, period = 1, factor a

In round 1, the scan reaches the end of the string with k = 1. The period j - k = 5 is the length of abcdb, and the loop prints one copy because i = 0 <= k = 1 and then i moves to 5, which is past k. In round 2, the single character a is the only factor.

Why it is linear

The index j never moves back. After each round, the next round starts at a position close to the old j, so the part scanned twice is at most one period long, and the periods printed together cover the string once. So the total number of comparisons is O(n). Here the argument is only sketched. The run time in the next section is the check that matters in practice.

Smallest rotation

The rule

Put the string twice in a row, t = s + s. Every rotation of s is a substring of t of length n. Run Duval's scan on t, but only start new rounds at positions i < n. The smallest rotation starts at the last round start that is below n.

The method rests on the fact that the smallest rotation starts at a Lyndon factor boundary of t. The code keeps the last such start below n in ans. This lesson does not prove that fact. Section "Check against a brute force" tests the method on every string over three letters up to length 10, and on random longer strings.

A worked example: cabab

Take s = cabab. The rotations are cabab, ababc, babca, abcab, bcaba. The smallest is ababc, which starts at index 1. The program in section "The C++ code" prints:

$ printf 'cabab\n' | ./lyndon
factors: c ab ab
min rotation starts at 1: ababc

The factors of cabab itself are c, ab and ab. The smallest rotation starts at index 1, which is the start of the first ab factor (positions 1 and 2). Reading from there gives ab, then ab, then the c that was at the front.

Complexity

Building t = s + s costs O(n) memory, and the scan over t costs O(n) time. The doubled string holds 2n characters, which is still O(n). Reading s[i % n] would avoid the copy, but the simple version is easier to check.

The C++ code

The header below has both functions and the brute force used in the tests. It needs only the standard C++17 headers. Compile with g++ -std=c++17 -O2.

#include <bits/stdc++.h>
using namespace std;
 
// Duval's factorisation: s = w1 w2 ... wk with w1 >= w2 >= ... >= wk, each wi a Lyndon word.
// Runs in O(n) time.
vector<string> duval_factorise(const string& s) {
    int n = s.size();
    vector<string> res;
    int i = 0;
    while (i < n) {
        int j = i + 1, k = i;
        // s[i..j) is a prefix of the form (u)^t u' with u Lyndon
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j]) k = i;
            else k++;
            j++;
        }
        while (i <= k) {
            res.push_back(s.substr(i, j - k));
            i += j - k;
        }
    }
    return res;
}
 
// Index where the lexicographically smallest rotation of s starts. O(n).
// Uses the same loop on s+s, and keeps the last start position below n.
int min_rotation_start(const string& s) {
    int n = s.size();
    string t = s + s;
    int ans = 0, i = 0;
    while (i < n) {
        ans = i;
        int j = i + 1, k = i;
        while (j < 2 * n && t[k] <= t[j]) {
            if (t[k] < t[j]) k = i;
            else k++;
            j++;
        }
        while (i <= k) i += j - k;
    }
    return ans;
}
 
// Brute force: a Lyndon word is strictly smaller than every proper suffix.
bool is_lyndon_brute(const string& w) {
    if (w.empty()) return false;
    for (size_t p = 1; p < w.size(); p++)
        if (!(w < w.substr(p))) return false;
    return true;
}
 
// Brute force smallest rotation: compare all n rotations.
string min_rotation_brute(const string& s) {
    int n = s.size();
    string best = s;
    for (int i = 1; i < n; i++) {
        string r = s.substr(i) + s.substr(0, i);
        if (r < best) best = r;
    }
    return best;
}

The main program reads one string and prints the factorisation and the smallest rotation:

#include "lyndon.hpp"
 
int main() {
    string s;
    cin >> s;
    vector<string> f = duval_factorise(s);
    cout << "factors:";
    for (auto& w : f) cout << " " << w;
    cout << "\n";
    int st = min_rotation_start(s);
    string rot = s.substr(st) + s.substr(0, st);
    cout << "min rotation starts at " << st << ": " << rot << "\n";
    return 0;
}

Outputs from the same program on the sample strings used in this lesson:

$ printf 'abcdba\n' | ./lyndon
factors: abcdb a
min rotation starts at 5: aabcdb
$ printf 'cabab\n' | ./lyndon
factors: c ab ab
min rotation starts at 1: ababc
$ printf 'bbaab\n' | ./lyndon
factors: b b aab
min rotation starts at 2: aabbb
$ printf 'abab\n' | ./lyndon
factors: ab ab
min rotation starts at 0: abab

The string abab shows the tie case. Its rotations starting at 0, 1, 2 and 3 are abab, baba, abab and baba. Starts 0 and 2 both give the minimum abab, and this program returns 0. Any start whose rotation equals the minimum is correct, so compare the rotation strings, not the indices, when you test.

Trace in Python

A Python version is fast enough for small strings and for reading the logic. This program has no input. It prints the outer rounds of Duval's scan and the smallest rotation for abcdba. Run it with python3 -I duval_trace.py.

Python · editable

The output on the machine used for this lesson:

outer i=0: scanned to j=6, k=1, period=5
outer i=5: scanned to j=6, k=5, period=1
factors: ['abcdb', 'a']
smallest rotation: aabcdb starts at 5

Here the printed factors list is Python's list display. The C++ program prints the same pieces separated by spaces.

Speed

The C++ program was run on a random string of 200000 letters from a and b. Output was cut for display, and the timing covers the whole run:

$ time (./lyndon < big_duval.txt | cut -c1-40)
0.01s user 0.01s system 59% cpu 0.027 total

On this machine the run took about 0.03 s. The time on your machine will differ, but it should grow in step with n and not with n^2.

Check against a brute force

The stress test tries two kinds of input. First, every string over the letters a, b, c of length 0 to 10. That is 1 + 3 + ... + 3^10 = 88573 strings. For each one it checks three things: the factors concatenate back to the string, each factor is a Lyndon word by the brute check, and the factors are in non-increasing order. It also checks that the smallest rotation equals the brute force rotation. Second, it runs 20000 random strings of length up to 80, over alphabets of one to five letters.

$ ./lyndon_stress
all 108573 cases agree with brute force

The brute force for the rotation compares all n rotations, so it is O(n^2) time per string and is used only on short input.

What was checked here: the factorisation concatenates back to the input, every factor is Lyndon by the brute check, and the factors are non-increasing, for all 88573 strings up to length 10 and for 20000 random strings. The smallest rotation matches the brute force on the same inputs. Nothing beyond those runs has been checked.

Common mistakes

Comparing rotation indices instead of rotation strings. Two indices can give equal rotations in a periodic string, such as abab. A test that expects one specific index fails on a correct answer. Compare the strings.
Reading past the doubled string. The loop must stop at j < 2 * n. Without this check, t[j] reads outside the string. The symptom is garbage in the answer, or a crash on some inputs.
Taking the first start instead of the last one below n. The code keeps ans updated in every round, so the last round that starts below n gives the answer. Returning the first round's index gives a wrong rotation on strings such as cabab.
Forgetting that the factor length is j - k, not j - i. On abcdba the first round has i = 0 and j = 6, so j - i gives the whole string abcdba, which is not a Lyndon word. The correct length is j - k = 5, giving abcdb.
Calling a string Lyndon because it is sorted or because its first letter is the smallest. The test is against every proper suffix, so aba fails even though it starts with its smallest letter.
Building all n rotations for large n. That uses O(n^2) memory. The symptom is a memory error or a time limit on the largest test.

Checklist

Write the brute force first: compare all rotations, and check Lyndon words against every proper suffix.
Test the factorisation by checking that the factors concatenate back to the input, that each factor is Lyndon, and that the factors are non-increasing.
Test the rotation by comparing the rotation strings, not the indices.
Test periodic strings such as abab, aaaa and abcabc by hand.
Check the loop bounds: j < 2 * n for the doubled string, and i < n for the round starts.
Time the largest input and check that the time grows in step with n.
Keep the factor length as j - k in both the factorisation and the rotation code.

Summary

A Lyndon word is strictly smaller than each of its proper suffixes, and every string factors uniquely into non-increasing Lyndon words. Duval's scan finds that factorisation in O(n) by tracking the period of the current block. The smallest rotation of a cyclic string comes from the same scan run on the string written twice, keeping the last round start below n. Both were checked against brute force on every string over three letters up to length 10, plus random tests.

Practice

Problem 1: factorise by hand

Factorise bbaab into non-increasing Lyndon words. Then check your answer with the program.

Show the answer

Hint: start with the single letters. Each letter b is Lyndon on its own, and aab is Lyndon.

Answer: b, b, aab. The factors are non-increasing, b >= b >= aab, and they concatenate to bbaab. The program prints factors: b b aab.

Problem 2: smallest rotation of cabab

Find the lexicographically smallest rotation of cabab, and the index where it starts in cabab.

Show the answer

Hint: write down the five rotations, one for each starting index from 0 to 4, and compare them letter by letter.

Answer: ababc, starting at index 1. The program prints min rotation starts at 1: ababc.

Problem 3: which strings are Lyndon

Decide whether aabab is a Lyndon word. Then decide whether abab is one. Explain each answer using the definition.

Show the answer

Hint: a Lyndon word must be strictly smaller than each of its proper suffixes. Check the suffixes starting at position 1, 2, and so on.

Answer: aabab is Lyndon, because each proper suffix (abab, bab, ab, b) is larger than aabab. abab is not Lyndon, because its suffix ab is a prefix of abab, so abab is larger than ab.

Problem 4: count distinct rotations

Count the distinct rotations of abab. Say what the count tells you about how abab is built.

Show the answer

Hint: list the four rotations (starting at 0, 1, 2 and 3) and remove the repeats.

Answer: 2. The rotations are abab, baba, abab and baba, so two are distinct. The count is small because abab is ab written twice, so its rotations repeat.

Problem 5: smallest rotation with a tie

For the string bbaba, find the smallest rotation and its start index. Then say which index a correct solution could also return for this string, and why.

Show the answer

Hint: the rotation starting at index 2 is aba followed by bb.

Answer: ababb, starting at index 2. The program prints min rotation starts at 2: ababb. This string has no repeated rotation, so index 2 is the only correct answer here. Ties happen only in periodic strings such as abab, where any index whose rotation equals the minimum is correct.