EasyStringString MatchingUpdated Sep 2026

796. Rotate String

Asked at Meta, Roblox

Difficulty

Easy

Time

O(n)

Space

O(n)

Pattern

String

Companies

2

Problem

You are given two strings, s and goal. A shift moves the first character of s to the very end, pushing every other character one step to the left. For example, one shift turns "abcde" into "bcdea".

Return true if you can turn s into goal by applying some number of shifts (zero shifts are allowed, so s == goal is always a valid answer). Otherwise return false.

The two strings must have the same length — a shift never changes the length, so different lengths mean the answer is immediately false.

Shifts move the string around a circle

sabcde01234Start: the first letter 'a' is about to move to theendafter 1 shiftbcdea01234One shift: 'a' wrapped around to the last positionafter 2 shiftscdeab01234Two shifts give "cdeab", which equals goal, so theanswer is true
Each shift pushes the first letter to the back. After 2 shifts, "abcde" becomes "cdeab".

Constraints

  • ●1 <= s.length, goal.length <= 100
  • ●s and goal consist of lowercase English letters only

Examples

Example 1
Inputs = "abcde", goal = "cdeab"
Outputtrue
WhyTwo shifts move "abcde" to "cdeab": first "bcdea", then "cdeab". So the answer is true.
Example 2
Inputs = "abcde", goal = "abced"
Outputfalse
Why"abced" swaps the last two letters of "abcde". No number of shifts can swap letters — shifts only move the whole string around a circle — so the answer is false.

Asked At

2 companies
CompanyDifficulty
MetaEasyView all Meta questions →
RobloxEasyView all Roblox questions →

How to Think About It

1

Brute force: try every rotation of s and compare with goal. A rotation by k means taking s[k:] + s[:k]. There are len(s) possible rotations, each comparison is O(n). Total: O(n²). Works but slow for large strings.

2

Key insight: if s is a rotation of goal, then s + s (concatenation of s with itself) will always contain goal as a substring. For example, s = "abcde", s+s = "abcdeabcde" which contains every rotation: "cdeab" is at index 2.

3

Why this works: rotating by k gives s[k:] + s[:k]. In s+s, the substring starting at index k of length n is exactly s[k:] + s[:k]. So all rotations appear consecutively in s+s.

4

Algorithm: first check if len(s) != len(goal) — if so, return false immediately. Then check if goal is a substring of s+s. This is O(n) using KMP or built-in substring search.

5

Edge cases: empty strings (both empty = true), single character strings (only rotation is itself), strings of different lengths (always false). Also note: s == goal is a valid rotation by 0.

Optimal Approach

Check if len(s) != len(goal) — if so, return false. Concatenate s + s to get a doubled string. Check if goal appears as a substring of s + s. If yes, return true; otherwise false.

Walkthrough with s = "abcde", goal = "cdeab":

  • Lengths match (both 5).
  • s + s = "abcdeabcde".
  • Does "cdeab" appear in "abcdeabcde"? Yes, at index 2.
  • Return true.

Walkthrough with s = "abcde", goal = "abced":

  • Lengths match.
  • s + s = "abcdeabcde".
  • "abced" does not appear.
  • Return false.

Time: O(n) — substring search (KMP) on a string of length 2n. Space: O(n) for the concatenated string.

Check goal inside s + s

s + s"cdeab"abcdeabcde0123456789s + s = "abcdeabcde"; the window starting at index 2 is exactly "cdeab"if lengths differ → falsebuild t = s + ssearch goal in tLength check first, then one substring search over the doubled stringrotation by k = s[k:] + s[:k]= t[k : k + n]so goal in (s + s) means yes
Every rotation of s appears as a length-n window inside s + s, so one substring search answers the question.
ComplexityTime O(n)Space O(n)The doubled string s + s has length 2n, and a linear substring search (KMP) over it costs O(n); the extra space holds that doubled string.

What Trips People Up in Real Interviews

1

Forgetting the length check. If len(s) != len(goal), no rotation is possible. Always check this first before the concatenation trick — otherwise you get false positives on substrings.

2

Using goal + goal instead of s + s. Both work mathematically, but check which one the interviewer expects. The trick is s + s contains all rotations of s, so you search for goal in s + s.

3

Assuming the strings are the same length without checking. The problem says they are, but in follow-ups or variations they might not be. Always validate.

4

Overcomplicating with actual rotation simulation. You do NOT need to generate every rotation. The concatenation trick reduces it to a single substring check.

5

Forgetting that rotation by 0 (no rotation) is valid. s rotated by 0 equals s itself, which should return true if s == goal.

Solution Code

O(n) time
def rotateString(s, goal):
    if len(s) != len(goal):
        return False
    return goal in (s + s)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Rotate String problem?

Given two strings `s` and `goal`, return `true` if `s` is a rotation of `goal`. A rotation means shifting all characters of `s` to the left by some number of positions and wrapping the overflow to the end. For example, "abcde" rotated by 2 becomes "cdeab".

How do you solve Rotate String?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Rotate String?

Rotate String is asked at Meta, Roblox. It is a easy difficulty problem.

What are common mistakes on Rotate String?
  • Forgetting the length check. If `len(s) != len(goal)`, no rotation is possible. Always check this first before the concatenation trick — otherwise you get false positives on substrings.
  • Using `goal + goal` instead of `s + s`. Both work mathematically, but check which one the interviewer expects. The trick is `s + s` contains all rotations of `s`, so you search for `goal` in `s + s`.
  • Assuming the strings are the same length without checking. The problem says they are, but in follow-ups or variations they might not be. Always validate.
  • Overcomplicating with actual rotation simulation. You do NOT need to generate every rotation. The concatenation trick reduces it to a single substring check.
  • Forgetting that rotation by 0 (no rotation) is valid. `s` rotated by 0 equals `s` itself, which should return `true` if `s == goal`.