Rotate String
Asked at Meta
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".
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Easy | View all Meta questions → |
How to Think About It
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.
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.
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.
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.
Visual walkthrough: s = "abcde", goal = "cdeab". s+s = "abcdeabcde". Does "cdeab" appear? Yes, at index 2. So s rotated by 2 gives goal. Return true.
If s = "abcde", goal = "abced": s+s = "abcdeabcde". "abced" does not appear. Return false.
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.
What Trips People Up in Real Interviews
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.
Solution Code
def rotateString(s, goal):
if len(s) != len(goal):
return False
return goal in (s + s)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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Rotate String?
Rotate String is asked at Meta. 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`.