Pattern Guide
Lyndon Factorization
"Every string = unique product of decreasing Lyndon words. Duval's algorithm O(n)."
A Lyndon word is a string strictly smaller than all its proper rotations. Every string has a unique Lyndon factorization: s = w₁w₂...wₖ where w₁ ≥ w₂ ≥ ... ≥ wₖ lexicographically and each wᵢ is a Lyndon word. Duval's algorithm computes this in O(n) time and O(1) space. Applications: finding the lexicographically smallest rotation, string decomposition, and combinatorics on words.
Problems you can solve with this pattern
3 problems · click any to start solving
// Returns array of [start, end) positions for each Lyndon word in s
function lyndonFactorization(s) {
const n = s.length;
const result = [];
let i = 0;
while (i < n) {
let j = i, k = i + 1;
while (k < n && s[j] <= s[k]) {
if (s[j] < s[k]) j = i; // restart comparison
else j++;
k++;
}
// s[i..k-1] can be extended; s[i..i+(k-j-1)] is a Lyndon word
while (i <= j) {
result.push([i, i + (k - j)]); // Lyndon word is s[i..i+(k-j)-1]
i += k - j;
}
}
return result;
}
// Lexicographically smallest rotation = starting point of the last Lyndon word
// in the factorization of s+s (Booth's algorithm via Lyndon)
function minRotation(s) {
const factors = lyndonFactorization(s + s);
// The last Lyndon word that starts in the first half
let best = 0;
for (const [start] of factors) {
if (start < s.length) best = start;
else break;
}
return best;
}
// Check if string is a Lyndon word
function isLyndon(s) {
const n = s.length;
// A Lyndon word is strictly less than all its non-trivial rotations
for (let r = 1; r < n; r++) {
if (s.slice(r) + s.slice(0, r) <= s) return false;
}
return true;
}A Lyndon word is the lexicographically smallest string in its equivalence class of rotations. Examples: "a", "ab", "aab", "abb". Duval's algorithm: maintain current position i and "current Lyndon word" starting at some position. Compare s[i] with the next character expected by repeating the current Lyndon word. Build the factorization in-place in O(n) total comparisons.
// Returns array of [start, end) positions for each Lyndon word in s
function lyndonFactorization(s) {
const n = s.length;
const result = [];
let i = 0;
while (i < n) {
let j = i, k = i + 1;
while (k < n && s[j] <= s[k]) {
if (s[j] < s[k]) j = i; // restart comparison
else j++;
k++;
}
// s[i..k-1] can be extended; s[i..i+(k-j-1)] is a Lyndon word
while (i <= j) {
result.push([i, i + (k - j)]); // Lyndon word is s[i..i+(k-j)-1]
i += k - j;
}
}
return result;
}
// Lexicographically smallest rotation = starting point of the last Lyndon word
// in the factorization of s+s (Booth's algorithm via Lyndon)
function minRotation(s) {
const factors = lyndonFactorization(s + s);
// The last Lyndon word that starts in the first half
let best = 0;
for (const [start] of factors) {
if (start < s.length) best = start;
else break;
}
return best;
}
// Check if string is a Lyndon word
function isLyndon(s) {
const n = s.length;
// A Lyndon word is strictly less than all its non-trivial rotations
for (let r = 1; r < n; r++) {
if (s.slice(r) + s.slice(0, r) <= s) return false;
}
return true;
}- Strictly smallest among all rotations (not just ≤, but <)
- Any string can be uniquely factored into decreasing Lyndon words
- The factorization is computable in O(n) time, O(1) extra space
Duval's algorithm intuition: Maintain a "window" that is a power of the current candidate Lyndon word. When extending fails, extract complete Lyndon word copies from the window.
Applications:
- Lexicographically smallest rotation: the starting index of the first Lyndon word in the factorization of s+s
- String combinatorics: free Lie algebra basis elements are Lyndon words
- Generating necklace representatives for equivalence classes