Patterns/Part V - Strings, Sequences & Grid/Lyndon Factorization

Pattern Reference

Lyndon Factorization

"Split string into Lyndon words (non-increasing). Duval's algorithm. Minimal rotation, necklace computation."

Loading...

Deep Dive Tutorial

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.

Duval's Lyndon factorization algorithm
// 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;
}

Worked Problems

1
Lexicographically Smallest Rotation
Hard
Solve ↗
2
Concatenated Words
Hard
Solve ↗
3
Distinct Subsequences
Hard
Solve ↗
text
Lyndon word properties:
- 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
← All Patterns