Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.
A shift on s consists of moving the leftmost character of s to the rightmost position.
s = "abcde", then it will be "bcdea" after one shift.Example 1:
Input: s = "abcde", goal = "cdeab" Output: true
Example 2:
Input: s = "abcde", goal = "abced" Output: false
Constraints:
1 <= s.length, goal.length <= 100s and goal consist of lowercase English letters.The key idea in Rotate String is understanding what a rotation means. Rotating a string moves characters from the front to the back while keeping their order intact. Instead of simulating every possible rotation, we can use a helpful observation: if a string s can be rotated to form goal, then goal must appear as a substring of s + s. Concatenating the string with itself contains all possible rotations as substrings.
First, check whether the two strings have the same length. If they do, create s + s and check whether goal exists inside it using a string matching operation. This avoids explicitly rotating the string multiple times. More advanced string matching techniques like KMP can also be applied for efficient pattern searching.
This approach significantly reduces unnecessary work compared to brute-force rotation checks and provides an elegant solution using standard string operations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Rotation Check | O(n^2) | O(1) |
| Concatenation + Substring Search (s + s) | O(n) | O(n) |
Ashish Pratap Singh
In this approach, we use the property that a rotated version of a string s can be found as a substring of s + s. This is because rotating doesn't change the length of the string and by concatenating the string to itself, every possible rotation is covered.
Time Complexity: O(n^2), where n is the length of the string, due to using strstr.
Space Complexity: O(n), for the doubled string.
1#include <string>
2#include <algorithm>
3
4class Solution {
5public:
6 bool rotateString(std::string s, std::string goal) {
7 if (s.length() != goal.length()) return false;
8 return (s + s).find(goal) != std::string::npos;
9 }
10};In the C++ solution, we first check if s and goal have the same length. If not, we return false. By concatenating s with itself, we can simply check whether goal is a substring of this new string. The find method returns true if goal is found, otherwise false.
This approach simulates rotating the string s multiple times (equal to its length) to check if it equals goal at any point. This is a straightforward but less efficient method compared to the concatenation method.
Time Complexity: O(n^2), because we check for each possible rotation of s for a match with goal.
Space Complexity: O(1), as no additional storage is used beyond some counters.
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Rotate String is a common easy-level interview question that tests understanding of string manipulation and pattern matching. Variations of this problem may appear in technical interviews at companies including FAANG-level organizations.
The optimal approach checks whether the target string appears inside the concatenation of the original string with itself (s + s). If both strings have the same length and the goal is a substring of s + s, then the rotation is possible. This method avoids explicitly generating all rotations.
Concatenating a string with itself contains every possible rotation as a contiguous substring. If the goal string is one of those rotations, it will naturally appear within this combined string. This insight makes the problem easy to solve with a substring search.
The problem mainly relies on string manipulation and string matching techniques. Basic substring search works well, but algorithms like KMP can be used for efficient pattern matching in linear time.
In Python, this solution generates each possible rotation of s and checks if any matches goal using slicing.