Rotation of Each Other

EasyTries & Strings

Problem

A circular display shows a message by scrolling it: each step moves the first character to the end. Given s and goal, return true if goal appears on the display after some number of steps (zero steps allowed).

Example 1

Input:
s = "abcde", goal = "cdeab"
Output:
true

Two steps: abcde → bcdea → cdeab.

Example 2

Input:
s = "abcde", goal = "abced"
Output:
false

Constraints

  • 1 ≤ s.length, goal.length ≤ 10^4
  • Lowercase English letters only.

Hint

Show the first hint

Write down all rotations of "abcd". Do they appear together somewhere?

Walkthrough

How to approach it

01Clarify before coding

  • Does zero steps count? Yes, s is a rotation of itself.
  • Different lengths? Then the answer is false.
  • Only lowercase letters? Yes.

02Brute force

Build each of the n rotations and compare it with goal.

Cost: O(n²): 10^4 rotations of 10^4 characters each.

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.