How to Learn Duval’s Algorithm: Lyndon Words, Factorization, Three Pointers and Linear-Time String Structure

Wait, What?

A long string can be broken into a unique ordered sequence of special words in linear time, using only three moving pointers.

Duval’s algorithm computes the Lyndon factorization of a string. At first this sounds like a narrow piece of string combinatorics. In practice it is an elegant lesson in greedy structure, lexicographic order, amortized reasoning and how a tiny amount of state can reveal deep regularity in text.

The algorithm is particularly valuable educationally because the code is short but the invariant is rich. That makes it perfect for learning the difference between “I can run this code” and “I understand why each pointer moves.”

Quick Answer

Learn Duval’s algorithm through lexicographic order → rotations → Lyndon words → unique non-increasing factorization → the i/j/k pointers → equal/greater/less comparison cases → factor emission → linear-time amortization → minimal rotation → implementation boundaries. Trace the pointers on paper before trying to memorize the loop.

1. What Is a Lyndon Word?

A non-empty string is a Lyndon word if it is strictly lexicographically smaller than each of its non-trivial rotations. For example, with ordinary alphabetic order, ab is Lyndon because ab < ba. A repeated word such as abab is not primitive and therefore cannot be Lyndon.

Equivalent formulations compare a Lyndon word with its proper suffixes. The exact statement depends on the convention being used, so professional code should define the ordering and representation clearly before implementing anything.

2. The Factorization Job

Every non-empty word has a unique factorization into Lyndon words arranged in non-increasing lexicographic order:

s = w1 w2 ... wk
where w1 >= w2 >= ... >= wk

Duval’s 1983 algorithm finds this factorization in O(n) time with constant extra working space apart from the output representation.

The uniqueness is important. This is not just “one convenient way” to cut the string. The Lyndon factorization is a canonical structural decomposition.

3. Why Three Pointers Are Enough

The standard implementation uses pointers often named i, j and k.

i marks the start of the region currently being factorized.
j scans forward into unexplored characters.
k compares the new character against an earlier position inside the candidate repeating structure.

The learner’s task is not merely to remember these names. At every loop iteration, be able to state what region is finalized, what region is currently being tested, and why k points where it does.

4. The Three Comparison Cases

Inside a factorization phase, compare s[k] and s[j]. The exact inequality direction depends on the chosen implementation convention, but the structural cases are the same.

Equal: the repeating pattern can continue. Move both comparison positions forward.
New character is larger: the candidate can still form a Lyndon structure, but the comparison restarts from the beginning of the current region.
New character is smaller: the current candidate can no longer continue in the same way; the algorithm has enough information to emit one or more factors.

This is where many copied implementations become dangerous. If you reverse the ordering convention but forget to reverse the comparisons consistently, the code may still produce plausible output while violating the factorization theorem.

5. Standard Pseudocode

i = 0
while i < n:
    j = i + 1
    k = i

    while j < n and s[k] <= s[j]:
        if s[k] < s[j]:
            k = i
        else:
            k += 1
        j += 1

    factor_length = j - k
    while i <= k:
        output s[i : i + factor_length]
        i += factor_length

Do not treat this as language-independent magic. Test the exact inequality convention against known examples and document whether lexicographically smaller factors are considered “earlier.”

6. Hand-Trace Before Coding

Take a short string such as ababbab. Write the indices underneath. On every comparison, record i, j and k and the two characters being compared. When the inner loop stops, calculate j-k and mark the factors emitted by the outer loop.

This is more valuable than watching an animation passively. The learner should predict the next pointer movement, then verify it.

7. Why the Algorithm Is Linear

There are nested loops, so a first glance can suggest O(n²). That is the wrong conclusion. The scan pointer j moves forward through the string, and when work is repeated, the factor-emission step advances i by chunks that account for that repetition.

The correct proof is amortized: characters can participate in only a bounded amount of pointer work across the entire execution. Duval’s result gives a linear-time factorization rather than restarting a fresh substring comparison from every position.

This is an important professional habit: never infer complexity only from the visual nesting depth of loops.

8. Minimal Rotation Is a Natural Application

A closely related use of Lyndon structure is finding the lexicographically smallest cyclic rotation of a string. One practical method applies Duval-style reasoning to s+s while restricting candidate starts to the first n positions.

This matters in canonicalizing cyclic objects: necklaces, circular sequences, repeated schedules or representations where rotations should count as equivalent.

Keep the teaching jobs distinct, though. Lyndon factorization and minimal rotation are related, not identical contracts.

9. Why This Algorithm Complements, Rather Than Replaces, Other String Structures

eduKateSengkang already contains dedicated material on suffix arrays, suffix automata, FM-indexes, eertrees and general string matching. Duval’s algorithm serves a different job. It factors a string according to Lyndon structure; it is not a substring-search index and does not replace suffix-based machinery.

The connection is conceptual: all these algorithms reveal hidden order in strings by choosing a representation that turns repeated comparisons into reusable structure.

10. Alphabet Order Is Part of the Input Contract

In textbook examples, characters have a simple total order. Real software may involve Unicode, locale-dependent collation, case folding or custom symbol order. Those choices can change the factorization.

Professional practice therefore distinguishes code-point order, locale collation and domain-specific order. If canonical outputs must be portable across systems, define the ordering explicitly instead of relying on platform defaults.

11. Memory and Output Representation

The algorithm itself can work with O(1) auxiliary state, but returning every factor as a newly allocated substring can increase memory and copying costs. A production implementation may return index ranges or iterators instead.

This distinction is useful for learners: asymptotic workspace of the core algorithm is not always the same as memory consumed by a convenient API.

12. Testing Strategy

Test a one-character string.
Test all-equal characters.
Test strictly increasing and strictly decreasing strings.
Test periodic strings such as ababab.
After factorization, concatenate factors and verify the original string is recovered.
Verify every factor is Lyndon under the chosen definition.
Verify factors appear in the required non-increasing order.
Cross-check minimal rotation against brute force for short random strings.

13. A Learning Sequence That Exposes the Invariant

Research in programming education supports starting with prediction, tracing and worked examples before asking learners to construct a complex procedure independently. Duval’s algorithm is ideal for this approach because three small subgoals carry most of the reasoning.

Maintain the candidate Lyndon region.
Compare the next character against the correct position in the candidate pattern.
Emit repeated factors when the candidate can no longer extend.

Once those subgoals are stable, the compact code becomes a compression of understanding rather than a memorized trick.

Common Failure States

Calling any lexicographically small substring a Lyndon word without checking rotations.
Mixing up Lyndon factorization with arbitrary dictionary segmentation.
Reversing an inequality without updating the entire ordering convention.
Assuming nested loops imply quadratic time.
Allocating substrings repeatedly and then claiming the whole implementation uses constant space.
Using locale-dependent string comparison when canonical reproducibility is required.
Applying the minimal-rotation variant without restricting candidate starts correctly.

Practice Ladder

Beginner: identify which short words are Lyndon by comparing rotations.
Foundation: factor several strings manually and verify non-increasing factor order.
Intermediate: trace i, j and k on paper, then implement the standard linear algorithm.
Advanced: prove the amortized O(n) bound and return index ranges instead of copied substrings.
Professional: add a minimal-rotation routine, define a stable symbol-order contract, and differential-test against brute force on random inputs.
Explanation test: explain why the algorithm can emit repeated factors of length j-k.

Learning Hall Boundary

This article owns Duval’s algorithm, Lyndon words, Lyndon factorization, the three-pointer invariant and minimal-rotation connection. It does not replace existing suffix-array, suffix-automaton, FM-index, palindrome, regular-expression or general string-matching articles.

Evidence Boundary

Jean-Pierre Duval published “Factorizing Words over an Ordered Alphabet” in the Journal of Algorithms 4(4), 1983, pp. 363–381, presenting efficient Lyndon-factorization algorithms. Later combinatorics-on-words literature continues to use Duval’s linear-time method as a foundational result. Current algorithm references such as Algorithms for Competitive Programming provide a practical implementation-oriented description and minimal-rotation application. The teaching progression here is also informed by PRIMM research and by studies of subgoal-labelled worked examples in introductory programming.

Professional rule: you understand Duval’s algorithm when you can explain what i, j and k mean before every comparison, justify each reset, and prove why total pointer work remains linear.