The Rotate String problem asks us to check whether one string goal
can be obtained by rotating another string s
.
- A rotation means repeatedly moving the leftmost character of a string to the rightmost position.
- We need to return True if after some number of rotations,
s
can becomegoal
; otherwise return False.
Here’s the [Problem Link] to begin with.
Examples
Example 1
Input: s = "abcde", goal = "cdeab"
Output: true
Explanation: "abcde" → "bcdea" → "cdeab"
Example 2
Input: s = "abcde", goal = "abced"
Output: false
Explanation: No rotation of "abcde" equals "abced".
Intuition and Approach
To solve Rotate String, let’s analyze:
- Rotation property:
- If you rotate a string
s
, the result is always a substring of s+s. - Example:
s = "abcde"
→s+s = "abcdeabcde"
.- All possible rotations (
"abcde", "bcdea", "cdeab", "deabc", "eabcd"
) are substrings of"abcdeabcde"
.
- All possible rotations (
- If you rotate a string
- Algorithm:
- Check if lengths of
s
andgoal
are equal. If not, returnFalse
. - Create
string = s + s
. - If
goal
is a substring ofstring
, returnTrue
. Otherwise returnFalse
.
- Check if lengths of
This trick is both simple and optimal, avoiding the need to simulate rotations.
Code Implementation
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
string = s + s
return goal in string
Code Explanation
- Length check:
- If
s
andgoal
have different lengths, rotation is impossible.
- If
- Concatenate string:
s + s
contains all possible rotations ofs
.
- Substring check:
- If
goal
is ins+s
, thengoal
is a valid rotation. - Otherwise, return
False
.
- If
Dry Run
Input: s = "abcde"
, goal = "cdeab"
- Check lengths: both length = 5 → valid.
- Concatenate:
"abcde" + "abcde" = "abcdeabcde"
. - Check substring:
"cdeab"
in"abcdeabcde"
→ True.
Output: True
.
Time and Space Complexity
- Time Complexity:
- Concatenation takes O(N).
- Substring search takes O(N) (average, depending on implementation).
Overall: O(N), whereN
is the length of the string.
- Space Complexity:
- We create
s+s
, which takes O(N) extra space.
- We create
Conclusion
The Rotate String problem can be solved optimally using the property that all rotations of a string appear as substrings of s+s
.
- Avoids explicit rotation simulation.
- Runs in O(N) time and space.
- Clean and elegant one-liner:
return len(s) == len(goal) and goal in (s+s)
This solution is both interview-friendly and competitive programming optimal.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.