Is Rotate String easy or hard?

Rotate String is classified as an Easy problem. The brute force approach is straightforward, but recognizing the s + s substring trick is the key insight that simplifies the implementation and improves performance.

How to solve Rotate String in O(n)?

First verify that s and goal have the same length. Concatenate the string with itself to form s + s. If goal appears as a substring inside this new string, then a rotation exists. Substring search makes the overall time complexity O(n).

What is the best approach for Rotate String?

The most efficient approach uses the concatenation trick. If two strings have the same length, check whether goal appears as a substring of s + s. Every rotation of a string exists within this doubled string. This solution runs in O(n) time with O(n) extra space.

What data structure is used in Rotate String?

The problem primarily relies on basic string operations. The optimal solution uses string concatenation and substring search, which internally relies on string matching algorithms such as optimized pattern search techniques.

What is the time complexity of Rotate String?

The optimal solution runs in O(n) time using a substring search on s + s, where n is the length of the string. The brute force rotation simulation takes O(n²) time because up to n rotations are generated and each comparison takes O(n).

Is Rotate String asked at Google, Amazon, or Meta?

Rotate String is a common entry-level string problem frequently used in coding screens and practice sets. Variants of rotation and substring checks appear in interviews at companies like Amazon and Google because they test understanding of string manipulation and pattern recognition.

How do you write a Rotate String solution in Python or Java?

In Python or Java, concatenate the string with itself and check if goal exists in the result. For example, in Python: return len(s) == len(goal) and goal in (s + s). Java solutions typically use (s + s).contains(goal) after verifying the lengths match.

Description Solution Video 16:46

796. Rotate String

Easy66.6% acceptance12 companies

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.

Asked at 12 companies

NatWest Wells Fargo Rivian Amazon Microsoft Bloomberg

Google Meta Oracle Zoho Accenture

TCS

Topics

String String Matching

16:46

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def rotateString(self, s: str, goal: str) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"abcde"
"cdeab"

Input

"abcde"
"abced"

Your code is saved on this device.Solution