Booth's Algorithm

Purpose: Find the rotation of a string that is lexicographically smallest (the least rotation), in $O(n)$ time and $O(n)$ space.

Two different "Booth's algorithms"

This page is about Booth’s least-rotation algorithm (1980). There is also Booth’s multiplication algorithm for signed binary multiplication in hardware — unrelated, and essentially never needed in competitive programming.

Algorithm

Booth’s original formulation runs a KMP failure function over the doubled string $s+s$ and tracks the index of the best rotation found so far.

The version everybody actually writes is the “smallest rotation” two-pointer (sometimes credited to Zhou / Shiloach), which is simpler and equally $O(n)$:

1. Keep two candidate start positions $i=0$, $j=1$, and an offset $k=0$.
2. Compare s[(i+k) % n] with s[(j+k) % n].
   • Equal → increment $k$ and keep comparing.
   • s[i+k] > s[j+k] → every start in $[i,i+k]$ is beaten; jump $i\leftarrow i+k+1$.
   • s[i+k] < s[j+k] → symmetrically, jump $j\leftarrow j+k+1$.
   • After a jump reset $k=0$, and if $i=j$ push $j$ forward by one.
3. Stop when $k=n$ or when the larger pointer reaches $n$. The answer is $\min (i,j)$.

Code

int leastRotation(const string& s) {
    int n = s.size(), 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 min(i, j);
}
 
string smallestRotation(const string& s) {
    int p = leastRotation(s);
    return s.substr(p) + s.substr(0, p);
}

Paradigm

Elimination / amortized two pointers. Every comparison either advances $k$ or eliminates $k+1$ candidate starting positions permanently.

Complexity

• Time: $O(n)$ — the sum of all $k$-advances and pointer jumps is bounded by $2n$
• Space: $O(1)$ for the index, $O(n)$ if you materialise the rotated string

Why It Works

Suppose the first $k$ characters of the rotations starting at $i$ and $j$ agree, and then s[i+k] > s[j+k]. Take any start $i^{\prime }\in [i,i+k]$. Its rotation begins with the suffix s[i'..i+k] of the matched block, and the rotation starting at $j+(i^{\prime }-i)$ begins with the identical block followed by the strictly smaller character. So $i^{\prime }$ is beaten by $j+(i^{\prime }-i)$ and can be discarded. Since we only ever discard provably-dominated candidates, the surviving pointer is a true minimiser. ∎

Variants / Use Cases

• Duval’s algorithm — the Lyndon-factorisation route to the same answer; equally $O(n)$ and often preferred because the code is shorter
• Canonical form of a cyclic string — compare necklaces, deduplicate cyclic sequences, hash cycles
• Largest rotation — flip the comparison
• Cyclic string matching — search a pattern in a circular text via $s+s$
• Graph / polygon canonicalisation — canonicalise a cycle’s vertex labels or a polygon’s vertex order before hashing