Rotate String — Solution in Python, Java & C++
Rotate String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Google.
Rotate String is an easy coding problem on strings and string matching, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Strings, String Matching
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two strings s and goal, return true if s can become goal after some number of left shifts.
A left shift moves the leftmost character to the end of the string.
Example 1
Input: s = "abcde", goal = "cdeab"
Output: true
Explanation: Two left shifts.
Example 2
Input: s = "abcde", goal = "abced"
Output: false
Example 3
Input: s = "a", goal = "a"
Output: true
Constraints
1 <= s.length, goal.length <= 40Both consist of lowercase English letters.
Hints for Rotate String
Hint 1
Every rotation of
sappears as a contiguous substring ofs + s.Hint 2
So the answer is just a length check plus a substring search.
Hint 3
Do not skip the length check —
"a"is a substring of"abab"without being a rotation of"ab".
How to solve Rotate String
Every rotation of s is a substring of s + s, so check the lengths and search.
Approach
- Return
falseif the lengths differ. - Return whether
goaloccurs ins + s.
Why it works
s + s contains each left shift of s as a window of length n starting at offsets 0..n-1, and a same-length substring of it must be one of those windows.
Complexity
- Time —
O(n) with a linear substring search - Space —
O(n)
Pitfalls
- Skipping the length check lets
"a"match inside"abab".
Reference solution
Python
def rotateString(s: str, goal: str) -> bool:
return len(s) == len(goal) and goal in s + sJava
public static boolean rotateString(String s, String goal) {
return s.length() == goal.length() && (s + s).contains(goal);
}C++
bool rotateString(string s, string goal) {
return s.size() == goal.size() && (s + s).find(goal) != string::npos;
}JavaScript
var rotateString = function(s, goal) {
return s.length === goal.length && (s + s).indexOf(goal) >= 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings