910. Smallest Rotation
A cyclic bracelet is engraved with lowercase letters, and the jeweller reads it by choosing any starting bead and going around the bracelet once, in a fixed direction. This produces a rotation of the string s: for a start index i the reading is s[i..n-1] followed by s[0..i-1].
Return the reading that comes first in dictionary (lexicographic) order among all n rotations of s. If several start indices give the same reading, it is of course the same string.
Generating and comparing all rotations is quadratic; aim for O(n) time and O(n) extra space, where n is the length of s.
Example 1
- Input:
- s = "dcbadcbe"
- Output:
- "adcbedcb"
- Explanation:
Among all rotations the smallest one in dictionary order is \"adcbedcb\".
Example 2
- Input:
- s = "lunarlun"
- Output:
- "arlunlun"
- Explanation:
Among all rotations the smallest one in dictionary order is \"arlunlun\".
Constraints
1 ≤ s.length ≤ 105
s consists of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)