Skip to main content
Talentd

Rotate String - Solution & Explanation

EasyStringString Matching10 min readAsked at: Amazon, Microsoft, Wells Fargo +9
Practice this problem

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.

Approach Overview

Problem Overview: You are given two strings s and goal. The task is to determine whether repeatedly rotating s (moving the first character to the end) can produce goal. If any number of rotations results in the target string, return true; otherwise return false.

Approach 1: Brute Force with Rotation Simulation (O(n²) time, O(1) space)

The straightforward way is to simulate every possible rotation of s. For each rotation, move the first character to the end and compare the new string with goal. Since a string of length n has exactly n possible rotations, you repeat this process up to n times. Each comparison takes O(n) time, leading to an overall time complexity of O(n²) while using constant extra space.

This approach clearly demonstrates the rotation behavior and is easy to reason about. However, it becomes inefficient for longer strings because every rotation requires rebuilding or comparing the full string. Still, it’s useful when first understanding the problem or when implementing a direct simulation using basic string operations.

Approach 2: Concatenation Check (O(n) time, O(n) space)

A key observation simplifies the problem: if you concatenate s with itself (s + s), every possible rotation of s appears as a substring of this combined string. For example, if s = "abcde", then s + s = "abcdeabcde", which contains "bcdea", "cdeab", and every other rotation.

The solution becomes simple. First check that s and goal have the same length. If not, a rotation can never match. If lengths match, compute s + s and check whether goal exists as a substring. Modern substring search implementations run in O(n) time on average using optimized string matching techniques. The additional concatenated string requires O(n) space.

This trick avoids explicitly generating each rotation. Instead, it leverages how rotations naturally appear within a doubled string. The result is cleaner code and significantly better performance compared with simulation.

Recommended for interviews: Interviewers usually expect the concatenation insight. The brute force rotation simulation shows you understand the mechanics of the problem, but recognizing that goal must be a substring of s + s demonstrates stronger pattern recognition and familiarity with common string problem tricks.

Approach 1: Concatenation Check

In this approach, we use the property that a rotated version of a string s can be found as a substring of s + s. This is because rotating doesn't change the length of the string and by concatenating the string to itself, every possible rotation is covered.

This C solution first checks if the lengths of s and goal are the same. If not, it immediately returns false. Then it creates a new doubled string by concatenating s with itself. It checks if goal is a substring of the concatenated string. If it is, true is returned; otherwise, false is returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the string, due to using strstr.
Space Complexity: O(n), for the doubled string.

Try this approach in the editor →

Approach 2: Brute Force with Rotation Simulation

This approach simulates rotating the string s multiple times (equal to its length) to check if it equals goal at any point. This is a straightforward but less efficient method compared to the concatenation method.

The C solution iteratively rotates the string by slicing it and recomposing it character by character to check if it matches goal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), because we check for each possible rotation of s for a match with goal.
Space Complexity: O(1), as no additional storage is used beyond some counters.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustPHP

Python

Java

C++

Go

TypeScript

Rust

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Concatenation Check

Time Complexity: O(n^2), where n is the length of the string, due to using strstr.
Space Complexity: O(n), for the doubled string.

Brute Force with Rotation Simulation

Time Complexity: O(n^2), because we check for each possible rotation of s for a match with goal.
Space Complexity: O(1), as no additional storage is used beyond some counters.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Rotation SimulationO(n²)O(1)Good for understanding rotation mechanics or when implementing a direct simulation
Concatenation Check (s + s substring)O(n)O(n)Best general solution; concise and optimal for interview settings

Video Solution

Rotate String | Something to learn | Leetcode 796 | codestorywithMIK • codestorywithMIK • 23,611 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Rotate String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring