Pattern Guide
String Rotations & Booth's Algorithm
"Lexicographically minimum rotation in O(n). Check rotation in O(n) via concatenation."
String rotation problems: (1) check if string A is a rotation of B — B is a rotation of A iff B is a substring of A+A; (2) find the lexicographically smallest rotation — Booth's algorithm in O(n); (3) generate all rotations. These techniques appear in circular buffer problems, DNA sequence analysis, and any problem asking about cyclic equivalence classes.
Problems you can solve with this pattern
4 problems · click any to start solving
// Booth's algorithm: find start index of lexicographically smallest rotation
// Returns index i such that s[i..]+s[..i-1] is the smallest rotation
function boothMinRotation(s) {
const n = s.length;
const t = s + s; // doubled string
const f = new Array(2 * n).fill(-1);
let k = 0; // current best start position
for (let j = 1; j < 2 * n; j++) {
let i = f[j - k - 1];
while (i !== -1 && t[j] !== t[k + i + 1]) {
if (t[j] < t[k + i + 1]) k = j - i - 1;
i = f[i];
}
if (t[j] !== t[k + i + 1]) {
if (t[j] < t[k]) k = j;
f[j - k] = -1;
} else {
f[j - k] = i + 1;
}
}
return k;
}
// Simple check: is B a rotation of A?
function isRotation(A, B) {
return A.length === B.length && (A + A).includes(B);
}
// All rotations of a string
function allRotations(s) {
const doubled = s + s;
return Array.from({length: s.length}, (_, i) => doubled.slice(i, i + s.length));
}Rotation check: A is a rotation of B iff len(A) = len(B) and A is a substring of B+B. O(n) with KMP/hashing. Booth's algorithm: find the starting index of the lexicographically smallest rotation in O(n) using a "canonical rotation" technique. Key insight: maintain a "current best" position and a comparison with a "challenge" position, advancing both along the doubled string.
// Booth's algorithm: find start index of lexicographically smallest rotation
// Returns index i such that s[i..]+s[..i-1] is the smallest rotation
function boothMinRotation(s) {
const n = s.length;
const t = s + s; // doubled string
const f = new Array(2 * n).fill(-1);
let k = 0; // current best start position
for (let j = 1; j < 2 * n; j++) {
let i = f[j - k - 1];
while (i !== -1 && t[j] !== t[k + i + 1]) {
if (t[j] < t[k + i + 1]) k = j - i - 1;
i = f[i];
}
if (t[j] !== t[k + i + 1]) {
if (t[j] < t[k]) k = j;
f[j - k] = -1;
} else {
f[j - k] = i + 1;
}
}
return k;
}
// Simple check: is B a rotation of A?
function isRotation(A, B) {
return A.length === B.length && (A + A).includes(B);
}
// All rotations of a string
function allRotations(s) {
const doubled = s + s;
return Array.from({length: s.length}, (_, i) => doubled.slice(i, i + s.length));
}- Check rotation: B in A+A, O(n) with KMP
- All rotations: doubled string approach, O(n) per rotation
- Minimum rotation: Booth's algorithm O(n)
- Equivalent circular strings: compare canonical (minimum) rotations
Booth's algorithm: Uses a failure function similar to KMP to avoid comparing the same characters repeatedly. The key invariant: k is always the starting position of the current lexicographically smallest rotation candidate.
Applications: Cyclic string equivalence, circular sequence alignment, rotating buffer problems, string period problems (smallest period = smallest rotation that is a rotation of itself).