Rotate String
EasyPrompt
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.
- For example, if
s = "abcde", then it will be"bcdea"after one shift.
Example 1:
Input: s = "abcde", goal = "cdeab"
Output: trueExample 2:
Input: s = "abcde", goal = "abced"
Output: false
Constraints:
1 <= s.length, goal.length <= 100sandgoalconsist of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the rotation process directly. We generate every possible rotation of the string s and check if any of these rotated strings match the goal string.
Algorithm
- First, check if the lengths of
sandgoalare different. If they are, returnfalseimmediately. - If
sandgoalare identical, returntrueas it requires zero shifts. - Iterate
ntimes, wherenis the length ofs. - In each iteration, create a new string by rotating the current version of
s. A rotation is performed by taking the substring from the second character to the end and appending the first character. - Compare the newly rotated string with
goal. If they are equal, returntrue. - If the loop completes without finding a match, return
false.
Walkthrough
The algorithm iterates through all possible shifts of string s. For a string of length n, there are n possible unique rotations (including the original string). In each iteration, we perform one shift on s and compare the result with goal.
A shift operation involves moving the first character to the end. For example, "abcde" becomes "bcdea". We can repeat this process n-1 times. If at any point the rotated string equals goal, we return true. If we complete all possible rotations without finding a match, it means goal cannot be obtained from s, so we return false.
An initial check is to ensure that s and goal have the same length. If they don't, a rotation is impossible.
class Solution { public boolean rotateString(String s, String goal) { if (s.length() != goal.length()) { return false; } if (s.equals(goal)) { return true; } String tempS = s; for (int i = 0; i < s.length(); i++) { // Perform one rotation tempS = tempS.substring(1) + tempS.charAt(0); if (tempS.equals(goal)) { return true; } } return false; }}Complexity
Time
O(N^2), where N is the length of the string `s`. The loop runs N times. Inside the loop, string slicing (`substring`) and concatenation take O(N) time. String comparison (`equals`) also takes O(N) time. Thus, the total time complexity is N * O(N) = O(N^2).
Space
O(N), where N is the length of the string `s`. In each iteration, a new string of length N is created to store the rotated version. This requires O(N) auxiliary space.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem definition.
Cons
Inefficient for long strings due to repeated string creation and comparison in each iteration.
Solutions
Solution
class Solution {public boolean rotateString(String s, String goal) { return s.length() == goal.length() && (s + s).contains(goal); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.