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.Problem Overview: You are given two strings s and goal. The task is to determine whether repeatedly rotating s (moving the first character to the end) can produce goal. If any number of rotations results in the target string, return true; otherwise return false.
Approach 1: Brute Force with Rotation Simulation (O(n²) time, O(1) space)
The straightforward way is to simulate every possible rotation of s. For each rotation, move the first character to the end and compare the new string with goal. Since a string of length n has exactly n possible rotations, you repeat this process up to n times. Each comparison takes O(n) time, leading to an overall time complexity of O(n²) while using constant extra space.
This approach clearly demonstrates the rotation behavior and is easy to reason about. However, it becomes inefficient for longer strings because every rotation requires rebuilding or comparing the full string. Still, it’s useful when first understanding the problem or when implementing a direct simulation using basic string operations.
Approach 2: Concatenation Check (O(n) time, O(n) space)
A key observation simplifies the problem: if you concatenate s with itself (s + s), every possible rotation of s appears as a substring of this combined string. For example, if s = "abcde", then s + s = "abcdeabcde", which contains "bcdea", "cdeab", and every other rotation.
The solution becomes simple. First check that s and goal have the same length. If not, a rotation can never match. If lengths match, compute s + s and check whether goal exists as a substring. Modern substring search implementations run in O(n) time on average using optimized string matching techniques. The additional concatenated string requires O(n) space.
This trick avoids explicitly generating each rotation. Instead, it leverages how rotations naturally appear within a doubled string. The result is cleaner code and significantly better performance compared with simulation.
Recommended for interviews: Interviewers usually expect the concatenation insight. The brute force rotation simulation shows you understand the mechanics of the problem, but recognizing that goal must be a substring of s + s demonstrates stronger pattern recognition and familiarity with common string problem tricks.
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.
This C solution first checks if the lengths of s and goal are the same. If not, it immediately returns false. Then it creates a new doubled string by concatenating s with itself. It checks if goal is a substring of the concatenated string. If it is, true is returned; otherwise, false is returned.
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.
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.
The C solution iteratively rotates the string by slicing it and recomposing it character by character to check if it matches goal.
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.
| Approach | Complexity |
|---|---|
| Concatenation Check | Time Complexity: O(n^2), where n is the length of the string, due to using strstr. |
| Brute Force with Rotation Simulation | Time Complexity: O(n^2), because we check for each possible rotation of |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Rotation Simulation | O(n²) | O(1) | Good for understanding rotation mechanics or when implementing a direct simulation |
| Concatenation Check (s + s substring) | O(n) | O(n) | Best general solution; concise and optimal for interview settings |
LeetCode Rotate String Solution Explained - Java • Nick White • 21,237 views views
Watch 9 more video solutions →Practice Rotate String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor