1844. The Smallest Rotation

Rotating s by k places means taking s[k..] followed by s[..k]. Among the n rotations, one is smallest in dictionary order, possibly tied with others. Print the SMALLEST k that produces it.

bcabc -> 2 abcbc abcde -> 0 already smallest aaaa -> 0 every rotation is the same, so the smallest k wins abab -> 0 rotations 0 and 2 are identical banana -> 5 abanan abaab -> 2 aabab

abaab is the one to check. Three positions hold an a, at 0, 2 and 3. Picking the first one gives abaab, but rotating at 2 gives aabab, which is smaller. Choosing the first smallest CHARACTER is not enough; that version was run on this input and answers 0.

## What most people try first

Build all n rotations and compare. Each rotation costs n to build and n to compare, so O(n^2): 4 * 10^10 character operations at n = 200000. The method below is about 1.4 * 10^8.

## Every rotation is a block of the doubled string

Write s twice. The n characters of s + s starting at position k, for any k from 0 to n-1, are exactly rotate(s, k). So sorting the suffixes of s + s ranks every rotation, and the first suffix in sorted order whose start is below n names a smallest rotation.

d = s + s sa = suffix array of d p = the first entry of sa with p < n R = d[p .. p+n-1] a smallest rotation answer = the first position of R inside d that is below n

## Why the last step is needed

Sorting the suffixes ranks them by their WHOLE contents, not by their first n characters, so among several positions producing the same smallest rotation the suffix array may put any of them first. That is not a defect in the sort: two suffixes with the same first n characters are separated by what follows, and nothing GUARANTEES that the earlier position wins. abab has rotations 0 and 2 identical, and the suffix at 2 is longer, so it may well sort before the suffix at 0.

Searching for R inside d with the prefix function of problem 1802 and taking the first hit below n fixes the tie, in O(n).

## Why positions at or beyond n need no separate handling

d has period n, so any block of length n starting at k >= n is identical to the one starting at k - n. Scanning left to right and stopping at the first hit below n therefore finds the true smallest k.

## Cost

O(n log^2 n) for the suffix array over 2n characters, about 1.4 * 10^8 operations at the limits, plus O(n) for the search.

Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - if several rotations tie for smallest, the smallest such `k` is wanted - a rotation is not an occurrence, so overlap does not arise, and one shift amount is wanted