796. Rotate String
Rotate String (LeetCode 796) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Naive / KMP / Rabin-Karp subpattern.
How to solve Rotate String
Rotate String is a String Matching problem, part of String Manipulation Patterns. Master string matching algorithms including naive search, KMP pattern matching, and Rabin-Karp hashing.
Work towards the solution in these steps:
- Think about how string rotations relate to substrings and how you can verify if one string is a rotation of another.
- Consider concatenating the original string with itself to capture all possible rotations as substrings.
- Check if the goal string exists as a substring within this doubled string to determine if a rotation is possible.
The reference solution runs in O(n) time and O(1) space.
The Rotate String solution and editorial walks through the full approach with reference code.
Problem statement
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: true
Example 2:
Input: s = "abcde", goal = "abced" Output: false
Constraints:
- 1 <= s.length, goal.length <= 100
- s and goal consist of lowercase English letters.
Topics and companies
Topics: String, String Matching.
Reported in interviews at Amazon, Microsoft, Oracle.
How to practise Rotate String on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Rotate String in the code editor, or read the Rotate String editorial for a worked solution with its approach and complexity analysis.
Where Rotate String sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Naive / KMP / Rabin-Karp subpattern
- The full DSA patterns sheet
Problems related to Rotate String
Other problems that use the same Naive / KMP / Rabin-Karp and String Manipulation Patterns techniques:
- Find Beautiful Indices in the Given Array II — Hard, same subpattern
- Find the Index of the First Occurrence in a String — Easy, same subpattern
- Longest Common Prefix — Easy, same subpattern
- Repeated String Match — Medium, same subpattern
- Shortest Palindrome — Hard, same subpattern
- Add Strings — Easy, same pattern
Rotate String FAQ
What is the LeetCode number of Rotate String?
Rotate String is LeetCode problem 796, rated Easy.
What pattern is used to solve Rotate String?
Rotate String is a String Matching problem. It belongs to the String Manipulation Patterns pattern, in the Naive / KMP / Rabin-Karp subpattern.
What is the time complexity of Rotate String?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Rotate String?
Rotate String has been reported in interviews at Amazon, Microsoft, Oracle.