# LeetCode 796: Rotate String

## Problem Restatement

We are given two strings:

```python
s
goal
```

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

For example:

```text
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:

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

## Examples

Example 1:

```python
s = "abcde"
goal = "cdeab"
```

Apply two shifts:

```text
abcde -> bcdea -> cdeab
```

So the answer is:

```python
True
```

Example 2:

```python
s = "abcde"
goal = "abced"
```

No sequence of left rotations can produce `"abced"`.

The answer is:

```python
False
```

Example 3:

```python
s = "abc"
goal = "abc"
```

Zero shifts are allowed.

The answer is:

```python
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:

```text
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:

```python
s + s
```

For example:

```python
s = "abcde"
s + s = "abcdeabcde"
```

The rotations are visible inside the doubled string:

```text
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:

```python
s = left + right
goal = right + left
```

The doubled string is:

```python
s + s = left + right + left + right
```

This contains:

```python
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

```python
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:

```python
len(s) == len(goal)
```

A rotation never changes string length.

Then we check whether `goal` appears in the doubled string:

```python
goal in s + s
```

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

## Simulation Version

This version follows the operation directly.

```python
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

```python
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 |