Earliest Smallest Rotation

HardArrays & Hashing

Problem

A circular name tag can be read starting at any of its n letters. Reading s from index k gives the rotation s[k:] + s[:k].

Return the index k whose rotation is lexicographically smallest. If several rotations are equally small (the string repeats a pattern), return the smallest such k. Aim for O(n) time.

Example 1

Input:
s = "bca"
Output:
2

Rotations: bca, cab, abc. The smallest, abc, starts at 2.

Example 2

Input:
s = "abab"
Output:
0

Rotations 0 and 2 are both abab; return the earlier one.

Example 3

Input:
s = "baba"
Output:
1

Constraints

  • 1 ≤ s.length ≤ 10^5
  • s consists of lowercase English letters.

Hint

Show the first hint

Comparing every pair of rotations letter by letter is O(n²) in the worst case (think 'aaaa…ab'). Can one comparison rule out many starting points?

Walkthrough

How to approach it

01Clarify before coding

  • Ties? Return the smallest index among equally small rotations.
  • Indices wrap around? Yes, read s circularly.
  • Size? Up to 10^5, so an O(n²) comparison of all rotations is too slow.

02Brute force

Generate all n rotations and keep the smallest (or compare candidates letter by letter).

Cost: O(n²) time: each comparison can take O(n) letters, e.g. for 'aaa…ab'.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.