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

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

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: