LeetCode 796: Rotate String

Problem Restatement

We are given two strings:

s
goal

A shift on s means moving the leftmost character to the rightmost position.

For example:

abcde -> bcdea

We need to return True if s can become goal after some number of shifts. Otherwise, return False.

Zero shifts are allowed, so if s == goal, the answer is True.

Input and Output

Item	Meaning
Input	Two strings s and goal
Output	True if goal is a rotation of s, otherwise False
Operation	Move the first character of s to the end
Allowed shifts	Any number, including zero
Constraint	Both strings contain lowercase English letters

Function shape:

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        ...

Examples

Example 1:

s = "abcde"
goal = "cdeab"

Apply two shifts:

abcde -> bcdea -> cdeab

So the answer is:

True

Example 2:

s = "abcde"
goal = "abced"

No sequence of left rotations can produce "abced".

The answer is:

False

Example 3:

s = "abc"
goal = "abc"

Zero shifts are allowed.

The answer is:

True

First Thought: Simulate All Rotations

A direct approach is to rotate s one step at a time.

For each rotation, check whether it equals goal.

For example:

abcde
bcdea
cdeab
deabc
eabcd

If any rotation equals goal, return True.

This works, but it performs repeated string slicing and comparison.

Key Insight

All rotations of s appear as substrings inside:

s + s

For example:

s = "abcde"
s + s = "abcdeabcde"

The rotations are visible inside the doubled string:

abcdeabcde
abcde
 bcdea
  cdeab
   deabc
    eabcd

So goal is a rotation of s exactly when:

1. s and goal have the same length.
2. goal appears inside s + s.

Algorithm

1. If len(s) != len(goal), return False.
2. Build the doubled string s + s.
3. Return whether goal is a substring of s + s.

Correctness

If goal is a rotation of s, then goal is formed by cutting s at some position and swapping the two parts.

So for some split:

s = left + right
goal = right + left

The doubled string is:

s + s = left + right + left + right

This contains:

right + left

as a contiguous substring. Therefore, goal appears in s + s.

Conversely, if goal has the same length as s and appears inside s + s, then it must start at some position within the first copy of s. The length-len(s) substring starting there is exactly one cyclic rotation of s. Therefore, goal is a valid rotation.

So the algorithm returns True exactly when goal is a rotation of s.

Complexity

Let n = len(s).

Metric	Value	Why
Time	O(n) average	We build s + s and search for goal
Space	O(n)	The doubled string stores 2n characters

Depending on the string-search implementation, the theoretical worst case of substring search may vary, but this solution is the intended concise approach.

Implementation

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in s + s

Code Explanation

First, the lengths must match:

len(s) == len(goal)

A rotation never changes string length.

Then we check whether goal appears in the doubled string:

goal in s + s

If both conditions are true, goal is a rotation of s.

Simulation Version

This version follows the operation directly.

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False

        current = s

        for _ in range(len(s)):
            if current == goal:
                return True

            current = current[1:] + current[0]

        return False

This is easier to connect to the problem statement, but less concise.

Testing

def run_tests():
    sol = Solution()

    assert sol.rotateString("abcde", "cdeab") is True
    assert sol.rotateString("abcde", "abced") is False
    assert sol.rotateString("abc", "abc") is True
    assert sol.rotateString("a", "a") is True
    assert sol.rotateString("aa", "aa") is True
    assert sol.rotateString("abc", "cab") is True
    assert sol.rotateString("abc", "acb") is False
    assert sol.rotateString("abc", "abcd") is False

    print("all tests passed")

run_tests()

Test coverage:

Test	Why
"abcde" to "cdeab"	Standard valid rotation
"abcde" to "abced"	Same characters but invalid order
Same string	Zero shifts
Single character	Smallest input
Repeated characters	Rotation with duplicates
"abc" to "cab"	Last rotation position
Different lengths	Impossible immediately