796. Rotate String - Solution & Explanation

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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).

Q: 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.

Q: 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.

The problem

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.

Python

def rotateString(s: str, goal: str) -> bool:
    if len(s) != len(goal):
        return False
    return goal in (s + s)

Java

class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        String doubled = s + s;
        return doubled.contains(goal);
    }
}

C++

#include <string>
#include <algorithm>

class Solution {
public:
    bool rotateString(std::string s, std::string goal) {
        if (s.length() != goal.length()) return false;
        return (s + s).find(goal) != std::string::npos;
    }
};

JavaScript

var rotateString = function(s, goal) {
    if (s.length !== goal.length) return false;
    return (s + s).includes(goal);
};

#include <stdbool.h>
#include <string.h>

bool rotateString(char *s, char *goal) {
    int lenS = strlen(s);
    int lenGoal = strlen(goal);
    if (lenS != lenGoal) return false;
    char *doubled = (char *)malloc(2 * lenS + 1);
    strcpy(doubled, s);
    strcat(doubled, s);
    bool result = strstr(doubled, goal) != NULL;
    free(doubled);
    return result;
}

public class Solution {
    public bool RotateString(string s, string goal) {
        if (s.Length != goal.Length) return false;
        string doubled = s + s;
        return doubled.Contains(goal);
    }
}

For the Python solution, we first compare the lengths of s and goal. If they're unequal, we return False. Otherwise, we check if goal is a substring of the concatenated string s + s.

Complexity

Time Complexity: O(n), since checking membership in Python might be optimized.
Space Complexity: O(n), due to the concatenated 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.

Python

def rotateString(s: str, goal: str) -> bool:
    if len(s) != len(goal):
        return False
    for i in range(len(s)):
        rotated = s[i:] + s[:i]
        if rotated == goal:
            return True
    return False

Java

class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            String rotated = s.substring(i) + s.substring(0, i);
            if (rotated.equals(goal)) return true;
        }
        return false;
    }
}

C++

#include <string>

class Solution {
public:
    bool rotateString(std::string s, std::string goal) {
        if (s.length() != goal.length()) return false;
        size_t len = s.length();
        for (size_t i = 0; i < len; ++i) {
            bool match = true;
            for (size_t j = 0; j < len; ++j) {
                if (s[(i + j) % len] != goal[j]) {
                    match = false;
                    break;
                }
            }
            if (match) return true;
        }
        return false;
    }
};

JavaScript

var rotateString = function(s, goal) {
    if (s.length !== goal.length) return false;
    for (let i = 0; i < s.length; i++) {
        const rotated = s.slice(i) + s.slice(0, i);
        if (rotated === goal) return true;
    }
    return false;
};

#include <stdbool.h>
#include <string.h>

bool rotateString(char *s, char *goal) {
    int lenS = strlen(s);
    int lenGoal = strlen(goal);
    if (lenS != lenGoal) return false;
    for (int i = 0; i < lenS; i++) {
        bool match = true;
        for (int j = 0; j < lenS; j++) {
            if (s[(i + j) % lenS] != goal[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

public class Solution {
    public bool RotateString(string s, string goal) {
        if (s.Length != goal.Length) return false;
        int len = s.Length;
        for (int i = 0; i < len; i++) {
            string rotated = s.Substring(i) + s.Substring(0, i);
            if (rotated.Equals(goal)) return true;
        }
        return false;
    }
}

In Python, this solution generates each possible rotation of s and checks if any matches goal using slicing.

Complexity

Time Complexity: O(n^2), as the slicing is repeated n times and comparison is made.
Space Complexity: O(n), due to the creation of new strings with slicing operations.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function rotateString(s: string, goal: string): boolean {
    return s.length === goal.length && (goal + goal).includes(s);
}

func rotateString(s string, goal string) bool {
	return len(s) == len(goal) && strings.Contains(s+s, goal)
}

Rust

impl Solution {
    pub fn rotate_string(s: String, goal: String) -> bool {
        s.len() == goal.len() && (s.clone() + &s).contains(&goal)
    }
}

PHP

class Solution {
    /**
     * @param String $s
     * @param String $goal
     * @return Boolean
     */
    function rotateString($s, $goal) {
        return strlen($goal) === strlen($s) && strpos($s . $s, $goal) !== false;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Concatenation Check	Time Complexity: O(n), since checking membership in Python might be optimized. Space Complexity: O(n), due to the concatenated string.
Brute Force with Rotation Simulation	Time Complexity: O(n^2), as the slicing is repeated n times and comparison is made. Space Complexity: O(n), due to the creation of new strings with slicing operations.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force with Rotation Simulation	O(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

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.

Rotate String solution and explanation

The problem

Approach overview

Approach 1: Concatenation Check

Approach 2: Brute Force with Rotation Simulation

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Rotate String solution and explanation

The problem

Approach overview

Approach 1: Concatenation Check

Approach 2: Brute Force with Rotation Simulation

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems