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.
A more clever and efficient approach is to use string concatenation. If goal is a rotation of s, then goal must be a substring of s concatenated with itself (s + s).
Algorithm
- First, check if the lengths of
sandgoalare different. If they are, returnfalse. - Create a new string
s_concatenatedby concatenatingswith itself (i.e.,s + s). - Check if
s_concatenatedcontains thegoalstring. - Return the result of the containment check.
Walkthrough
This method is based on a simple observation. Let's say s can be split into two parts, A and B, such that s = A + B. A rotation of s would result in the string B + A. If we concatenate s with itself, we get s + s = (A + B) + (A + B). It's clear that the rotated string B + A is a substring of A + B + A + B.
For example, if s = "abcde" and goal = "cdeab", we can see that s can be split into A = "ab" and B = "cde". The goal is B + A. The concatenated string s + s is "abcdeabcde". We can easily find "cdeab" within this concatenated string.
The algorithm is straightforward:
- Check if
sandgoalhave the same length. If not, returnfalse. - Create a new string by concatenating
swith itself. - Check if this new string contains
goalas a substring. - Return the result of this check.
class Solution { public boolean rotateString(String s, String goal) { // 1. Check if lengths are equal if (s.length() != goal.length()) { return false; } // 2. Concatenate s with itself String concatenatedS = s + s; // 3. Check if goal is a substring of the concatenated string return concatenatedS.contains(goal); }}Complexity
Time
O(N), where N is the length of the strings. The check for length is O(1). String concatenation `s + s` takes O(N) time. The `contains` method, which performs substring search, typically uses an efficient algorithm like KMP, resulting in a time complexity of O(N) for searching a pattern of length N in a text of length 2N. Thus, the overall complexity is O(N). In some language implementations, this could be O(N^2) if a naive substring search is used, but for Java, it's generally considered efficient.
Space
O(N), where N is the length of the string `s`. We need to create a new string `s + s` which has a length of 2N, thus requiring O(N) space.
Trade-offs
Pros
Very efficient with a linear time complexity.
Concise and elegant one-liner solution (after the length check).
Cons
Requires extra space to store the concatenated string.
Solutions
Solution
class Solution {public boolean rotateString(String s, String goal) { return s.length() == goal.length() && (s + s).contains(goal); }}class Solution {public: bool rotateString(string s, string goal) { return s.size() == goal.size() && strstr((s + s).data(), goal.data()); }};class Solution: def rotateString( self, s: str, goal: str) -> bool: return len(s) == len(goal) and goal in s + sVideo 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.