Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Rotate String

EASYProblemSolveExternal Links

Description

Given two strings s and goal, determine whether s can become goal after performing some number of left shifts.

A single left shift on a string means taking the leftmost character and moving it to the rightmost position. For instance, if s = "abcde", one left shift produces "bcdea".

Return true if s can become goal after zero or more shifts, or false otherwise.

Examples

Example 1

Input: s = "abcde", goal = "cdeab"

Output: true

Explanation: If we shift s to the left two times, we get:

  • After 1st shift: "bcdea"
  • After 2nd shift: "cdeab"

This matches goal, so the answer is true.

Example 2

Input: s = "abcde", goal = "abced"

Output: false

Explanation: No matter how many times we shift s, we can never produce "abced". The characters appear in a different relative order than any rotation of s.

Example 3

Input: s = "a", goal = "a"

Output: true

Explanation: A string of length 1 shifted any number of times always remains the same. Since s already equals goal, the answer is true.

Constraints

  • 1 ≤ s.length, goal.length ≤ 100
  • s and goal consist of lowercase English letters.

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to actually perform the rotations one by one and check after each rotation whether the resulting string matches goal.

Imagine you have a circular necklace made of lettered beads. To check if another arrangement of beads could come from the same necklace, you rotate the necklace one bead at a time and compare after each rotation. If after going all the way around (n rotations for a string of length n) you still haven't found a match, the two arrangements are different.

Since a string of length n has exactly n distinct rotations (including the original), we need to check at most n rotations.

Step-by-Step Explanation

Let's trace through with s = "abcde", goal = "cdeab":

Step 1: First, check if lengths are equal. len(s) = 5, len(goal) = 5. They match, so we proceed.

Step 2: Rotation 0 — current string is "abcde". Compare with goal "cdeab". No match.

Step 3: Perform rotation 1 — move 'a' from front to back. String becomes "bcdea". Compare with "cdeab". No match.

Step 4: Perform rotation 2 — move 'b' from front to back. String becomes "cdeab". Compare with "cdeab". Match found!

Step 5: Return true.

Brute Force — Rotating One Character at a Time — Watch how we physically rotate the string by moving the front character to the back, then compare with the goal after each rotation.

Algorithm

  1. If s and goal have different lengths, return false immediately.
  2. For each rotation i from 0 to n-1:
    a. Rotate s by moving the first character to the end.
    b. If the rotated string equals goal, return true.
  3. If no rotation matches, return false.

Code

class Solution {
public:
    bool rotateString(string s, string goal) {
        if (s.size() != goal.size()) return false;
        
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s == goal) return true;
            // Rotate: move first character to end
            char first = s[0];
            s = s.substr(1) + first;
        }
        return false;
    }
};
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        
        current = s
        for i in range(len(s)):
            if current == goal:
                return True
            # Rotate: move first character to end
            current = current[1:] + current[0]
        
        return False
class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        
        String current = s;
        for (int i = 0; i < s.length(); i++) {
            if (current.equals(goal)) return true;
            // Rotate: move first character to end
            current = current.substring(1) + current.charAt(0);
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n²)

We perform up to n rotations. Each rotation involves creating a new string (O(n) substring operations), and each comparison of two strings of length n takes O(n) time. Therefore, the total time is O(n) rotations × O(n) per rotation = O(n²).

Space Complexity: O(n)

Each rotation creates a new string of length n, so we use O(n) extra space for the rotated string at any given time.

Why This Approach Is Not Efficient

The brute force approach checks all n rotations, and each check involves an O(n) string comparison, giving O(n²) total time. For n ≤ 100 this is perfectly acceptable, but the approach involves redundant work — each rotation recreates the entire string just to shift one character.

The key insight is that all rotations of a string are already contained as substrings within the string concatenated with itself. If we concatenate s with itself to form s + s, every possible rotation of s appears as a contiguous substring of this doubled string. This means instead of generating rotations one by one, we can simply check whether goal is a substring of s + s, which can be done in O(n) time.

Optimal Approach - Concatenation and Substring Check

Intuition

Here is a beautiful insight: when you write a string next to itself, all of its rotations magically appear inside.

Consider s = "abcde". If we form s + s = "abcdeabcde", look at all length-5 substrings starting at each position:

  • Position 0: "abcde" (rotation 0)
  • Position 1: "bcdea" (rotation 1)
  • Position 2: "cdeab" (rotation 2)
  • Position 3: "deabc" (rotation 3)
  • Position 4: "eabcd" (rotation 4)

Every single rotation of s is there! This happens because the concatenation wraps the string around — the end connects back to the beginning, exactly like a rotation would.

So instead of manually performing each rotation and comparing, we just need to check: is goal a substring of s + s? If yes, then goal is indeed a rotation of s.

We must also verify that s and goal have the same length beforehand — otherwise a shorter string could appear as a substring without being a valid rotation.

Step-by-Step Explanation

Let's trace through with s = "abcde", goal = "cdeab":

Step 1: Check lengths: len(s) = 5, len(goal) = 5. They are equal, so proceed.

Step 2: Concatenate s with itself: doubled = "abcde" + "abcde" = "abcdeabcde".

Step 3: Search for goal "cdeab" inside doubled string "abcdeabcde".

Step 4: Start scanning from position 0: substring "abcde" — does it start with 'c'? No, 'a' ≠ 'c'. Move on.

Step 5: Position 1: substring "bcdea" — starts with 'b', not 'c'. Move on.

Step 6: Position 2: substring "cdeab" — starts with 'c'. Check full match: c=c, d=d, e=e, a=a, b=b. All 5 characters match!

Step 7: goal found as substring at position 2. Return true.

Concatenation Trick — Finding Rotation as Substring — Watch how concatenating s with itself creates a doubled string that contains all rotations. We then search for goal inside this doubled string.

Algorithm

  1. If s and goal have different lengths, return false.
  2. Concatenate s with itself to form doubled = s + s.
  3. Check if goal is a substring of doubled.
  4. If yes, return true. Otherwise, return false.

Code

class Solution {
public:
    bool rotateString(string s, string goal) {
        if (s.size() != goal.size()) return false;
        
        string doubled = s + s;
        return doubled.find(goal) != string::npos;
    }
};
class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        
        return goal in (s + s)
class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) return false;
        
        String doubled = s + s;
        return doubled.contains(goal);
    }
}

Complexity Analysis

Time Complexity: O(n)

Concatenating the string takes O(n) time. The substring search (using built-in methods that typically employ optimized algorithms like KMP or similar) runs in O(n) time in the average and worst case. Overall: O(n).

Note: Depending on the language's internal substring search implementation, the worst case could be O(n²) for naive implementations, but most modern standard libraries use O(n) algorithms.

Space Complexity: O(n)

We create a new string doubled of length 2n, which requires O(n) additional space.