STEP 5 · STRINGS · DOUBLE TO UNCOIL · EASY

Rotate String

WHAT IT SAYS

Return true if s can be turned into goal by any number of left rotations (moving the leftmost character to the end).

WHAT IT'S REALLY ASKING

"Rotating a string never changes its characters — it only changes where you start reading. So all n rotations are windows onto the same cycle. Glue the string to its own tail and every one of those windows is sitting there, side by side, as a substring. The question stops being 'is it a rotation' and becomes 'does it occur'."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Generate every rotation and compare

O(n^2) time, O(n) space per rotation

Rotate s once, compare to goal; rotate again, compare; repeat n times. Each rotation is a slice-and-concatenate, each comparison is a walk down the string.

WHERE THE WORK IS WASTED — You materialise n different strings that are all the same string. The characters never change and their cyclic order never changes — the only thing that differs is where you started reading. So you are allocating n copies of one cycle, and then walking each copy from scratch, doing n^2 character reads over a structure that contains n characters.

KEY OBSERVATION — THE UNLOCKlink

Glue the string to itself and every rotation appears.

Write the rotation as a cut. Any rotation of s splits it as s = XY and produces YX — that is what 'move the front to the back' means, for whichever front X you chose. Now write down s + s. It is X Y X Y. Look at the window of length n that starts right where the second X begins... no, better: start reading at position |X|. You read Y, then you read X. That window is exactly YX — the rotation you wanted. Every cut point gives a different starting offset, from 0 to n-1, and each of those offsets opens a window of length n inside the doubled string. So s + s contains ALL n rotations of s, as substrings, laid out consecutively. You do not have to generate them — concatenation already did. Therefore: goal is a rotation of s if and only if goal occurs as a substring of s + s. The lengths must match too, and that is not a formality — 'ab' is a substring of 'abcabc' without being a rotation of 'abc'. Without the length check, every short string would look like a rotation of every long one that happens to contain it.

Substring search in the doubled string

O(n) time if the substring search is linear (KMP or Z), O(n) space for the doubled string

If the lengths differ, return false immediately. Otherwise return whether s + s contains goal. One concatenation, one substring search.

WHAT YOU TRADED — The elegance hides the real cost: 'contains' is O(n * m) with a naive scan, so the O(n) claim only holds if you use KMP, Z, or a language whose indexOf is linear — the trick moves the work rather than removing it. And you spend O(n) memory on the doubled string. The transferable lesson is the manoeuvre itself: when a structure is cyclic, cut the circle open by doubling it, and every wrap-around case turns into an ordinary linear one.

WATCH THE IDEA RUN

4end of s

goal cdeab

rotation shown -

strings built 0

s glued to itself. The characters never changed — the only thing this doubling did was make every possible starting point available at once.

step 1 / 5

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Double to Uncoil the Circle

YOU'LL SEE IT AGAIN WHEN

The structure is cyclic — rotations, circular arrays, wrap-around windows — so 'the end' and 'the beginning' are the same place, and your loops keep needing a modulo.
You are about to generate every rotation or shift explicitly, which means producing n copies of one cycle.
The real question is 'does this pattern occur somewhere in the cycle', which becomes an ordinary substring or sliding-window question the moment the circle is cut open.

SAME BLUEPRINT, DIFFERENT PROBLEM

Maximum Sum Circular SubarrayNext Greater Element II (circular)Repeated String MatchFind the Index of the First Occurrence in a String (KMP)

The bar isn't "solved it once." It's "could rebuild it from the observation."