# Rotate String
**Difficulty:** EASY
[External](https://leetcode.com/problems/rotate-string)
Canonical: https://scaleengineer.com/dsa/problems/rotate-string
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
**Companies:** [SAP](https://scaleengineer.com/companies/sap), [Visa](https://scaleengineer.com/companies/visa), [tcs](https://scaleengineer.com/companies/tcs), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo), [Amdocs](https://scaleengineer.com/companies/amdocs), [Rivian](https://scaleengineer.com/companies/rivian)
---
## 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.

# Approaches
## Brute-Force Simulation
This approach simulates the rotation process directly. We generate every possible rotation of the string `s` and check if any of these rotated strings match the `goal` string.
**Time:** O(N^2), where N is the length of the string `s`. The loop runs N times. Inside the loop, string slicing (`substring`) and concatenation take O(N) time. String comparison (`equals`) also takes O(N) time. Thus, the total time complexity is N * O(N) = O(N^2). · **Space:** O(N), where N is the length of the string `s`. In each iteration, a new string of length N is created to store the rotated version. This requires O(N) auxiliary space.
**Pros:** Simple to understand and implement.; Directly follows the problem definition.
**Cons:** Inefficient for long strings due to repeated string creation and comparison in each iteration.
### Explanation
The algorithm iterates through all possible shifts of string `s`. For a string of length `n`, there are `n` possible unique rotations (including the original string). In each iteration, we perform one shift on `s` and compare the result with `goal`.

A shift operation involves moving the first character to the end. For example, `"abcde"` becomes `"bcdea"`. We can repeat this process `n-1` times. If at any point the rotated string equals `goal`, we return `true`. If we complete all possible rotations without finding a match, it means `goal` cannot be obtained from `s`, so we return `false`.

An initial check is to ensure that `s` and `goal` have the same length. If they don't, a rotation is impossible.

```java
class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }
        if (s.equals(goal)) {
            return true;
        }

        String tempS = s;
        for (int i = 0; i < s.length(); i++) {
            // Perform one rotation
            tempS = tempS.substring(1) + tempS.charAt(0);
            if (tempS.equals(goal)) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- First, check if the lengths of `s` and `goal` are different. If they are, return `false` immediately.
- If `s` and `goal` are identical, return `true` as it requires zero shifts.
- Iterate `n` times, where `n` is the length of `s`.
- In each iteration, create a new string by rotating the current version of `s`. A rotation is performed by taking the substring from the second character to the end and appending the first character.
- Compare the newly rotated string with `goal`. If they are equal, return `true`.
- If the loop completes without finding a match, return `false`.

## Simple Check with String Concatenation
A more clever and efficient approach is to use string concatenation. If `goal` is a rotation of `s`, then `goal` must be a substring of `s` concatenated with itself (`s + s`).
**Time:** O(N), where N is the length of the strings. The check for length is O(1). String concatenation `s + s` takes O(N) time. The `contains` method, which performs substring search, typically uses an efficient algorithm like KMP, resulting in a time complexity of O(N) for searching a pattern of length N in a text of length 2N. Thus, the overall complexity is O(N). In some language implementations, this could be O(N^2) if a naive substring search is used, but for Java, it's generally considered efficient. · **Space:** O(N), where N is the length of the string `s`. We need to create a new string `s + s` which has a length of 2N, thus requiring O(N) space.
**Pros:** Very efficient with a linear time complexity.; Concise and elegant one-liner solution (after the length check).
**Cons:** Requires extra space to store the concatenated string.
### Explanation
This method is based on a simple observation. Let's say `s` can be split into two parts, `A` and `B`, such that `s = A + B`. A rotation of `s` would result in the string `B + A`. If we concatenate `s` with itself, we get `s + s = (A + B) + (A + B)`. It's clear that the rotated string `B + A` is a substring of `A + B + A + B`.

For example, if `s = "abcde"` and `goal = "cdeab"`, we can see that `s` can be split into `A = "ab"` and `B = "cde"`. The `goal` is `B + A`. The concatenated string `s + s` is `"abcdeabcde"`. We can easily find `"cdeab"` within this concatenated string.

The algorithm is straightforward:
1. Check if `s` and `goal` have the same length. If not, return `false`.
2. Create a new string by concatenating `s` with itself.
3. Check if this new string contains `goal` as a substring.
4. Return the result of this check.

```java
class Solution {
    public boolean rotateString(String s, String goal) {
        // 1. Check if lengths are equal
        if (s.length() != goal.length()) {
            return false;
        }

        // 2. Concatenate s with itself
        String concatenatedS = s + s;

        // 3. Check if goal is a substring of the concatenated string
        return concatenatedS.contains(goal);
    }
}
```
### Algorithm
- First, check if the lengths of `s` and `goal` are different. If they are, return `false`.
- Create a new string `s_concatenated` by concatenating `s` with itself (i.e., `s + s`).
- Check if `s_concatenated` contains the `goal` string.
- Return the result of the containment check.

# Solutions
### Java

```java
class Solution {
public
  boolean rotateString(String s, String goal) {
    return s.length() == goal.length() && (s + s).contains(goal);
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool rotateString(string s, string goal) {
    return s.size() == goal.size() && strstr((s + s).data(), goal.data());
  }
};

```

### Python

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

```