# LeetCode 459: Repeated Substring Pattern

## Problem Restatement

We are given a string `s`.

We need to check whether `s` can be constructed by taking a non-empty substring and repeating it multiple times. The substring must be shorter than the whole string, because repeating the entire string once does not count. The official problem asks whether `s` can be built by appending multiple copies of a substring together.

For example:

```python
s = "abab"
```

This can be made by repeating `"ab"` twice:

```python
"ab" + "ab" = "abab"
```

So the answer is:

```python
True
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` |
| Output | `True` if `s` is made by repeating a smaller substring, otherwise `False` |
| Substring | Must be non-empty |
| Repeat count | Must be at least `2` |

Function shape:

```python
def repeatedSubstringPattern(s: str) -> bool:
    ...
```

## Examples

Example 1:

```python
s = "abab"
```

The substring `"ab"` repeated twice gives:

```python
"abab"
```

Answer:

```python
True
```

Example 2:

```python
s = "aba"
```

Possible proper substrings are:

```python
"a"
"ab"
```

Repeating `"a"` gives strings like `"aa"` or `"aaa"`.

Repeating `"ab"` gives strings like `"abab"`.

Neither gives `"aba"`.

Answer:

```python
False
```

Example 3:

```python
s = "abcabcabcabc"
```

This can be made by repeating `"abc"` four times:

```python
"abc" + "abc" + "abc" + "abc"
```

It can also be made by repeating `"abcabc"` twice.

Answer:

```python
True
```

## First Thought: Try Every Substring Length

A direct approach is to try every possible length for the repeated substring.

If `n = len(s)`, then the repeated substring length must be less than `n`.

Also, the length must divide `n`.

For example, if:

```python
s = "abcabcabcabc"
n = 12
```

valid candidate lengths are:

```python
1, 2, 3, 4, 6
```

Length `3` works because:

```python
"abc" * 4 == "abcabcabcabc"
```

Brute force code:

```python
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)

        for length in range(1, n):
            if n % length != 0:
                continue

            pattern = s[:length]
            if pattern * (n // length) == s:
                return True

        return False
```

This is simple and correct.

## Problem With Brute Force

The brute force method may build many repeated strings.

For every candidate length, it may compare up to `n` characters.

In the worst case, this costs about:

```python
O(n^2)
```

For this problem, that can still pass in many languages because the constraints are moderate, but there is a cleaner string trick.

## Key Insight

If `s` is made by repeating a smaller pattern, then `s` appears inside the middle of:

```python
s + s
```

after removing the first and last character.

For example:

```python
s = "abab"
s + s = "abababab"
```

Remove the first and last character:

```python
"bababa"
```

The original string `"abab"` appears inside `"bababa"`.

Why?

Because repeated strings remain unchanged under some rotation.

For `"abab"`, shifting left by two characters still gives `"abab"`:

```python
"abab" -> "abab"
```

That shift appears naturally inside `s + s`.

For a non-repeated string like:

```python
s = "aba"
```

we get:

```python
s + s = "abaaba"
(s + s)[1:-1] = "baab"
```

The original `"aba"` does not appear inside `"baab"`.

So the condition is:

```python
s in (s + s)[1:-1]
```

## Algorithm

Build the doubled string:

```python
doubled = s + s
```

Remove the first and last character:

```python
middle = doubled[1:-1]
```

Return whether `s` appears in `middle`:

```python
return s in middle
```

This works because we exclude the two trivial matches:

| Match | Why excluded |
|---|---|
| Start at index `0` | This is just the original `s` in `s + s` |
| Start at index `len(s)` | This is the second copy of `s` |

A match inside the middle means there is a non-trivial rotation equal to `s`, which happens exactly when `s` has a repeated substring pattern.

## Correctness

If `s` is made by repeating a substring `p`, then:

```python
s = p + p + ... + p
```

with at least two copies.

Shifting `s` left by `len(p)` characters gives the same string again, because the blocks are identical.

This shifted copy of `s` appears inside `s + s`, starting at index `len(p)`.

Since `0 < len(p) < len(s)`, this occurrence is inside `(s + s)[1:-1]`.

So the algorithm returns `True`.

Now suppose the algorithm returns `True`.

Then `s` appears inside `(s + s)[1:-1]`, which means there is a shift `k` where:

```python
0 < k < len(s)
```

and rotating `s` by `k` positions gives the same string.

A string equal to one of its non-trivial rotations must be periodic. Its repeating unit length divides the string into identical blocks.

Therefore, `s` can be built by repeating a smaller substring.

So the algorithm returns `True` exactly for strings with a repeated substring pattern.

## Complexity

Let `n = len(s)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` average in Python practice | String search is implemented efficiently |
| Space | `O(n)` | We build `s + s` and a sliced middle string |

A more conservative theoretical bound for generic substring search is `O(n^2)`, depending on the language and search implementation.

## Implementation

```python
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (s + s)[1:-1]
```

## Code Explanation

The expression:

```python
s + s
```

creates two copies of the string.

For example:

```python
"abab" + "abab" = "abababab"
```

The slice:

```python
[1:-1]
```

removes the first and last character.

This prevents matching the original string at the obvious positions.

Then:

```python
s in (s + s)[1:-1]
```

checks whether the original string appears at a non-trivial shifted position.

If it does, `s` has a repeated substring pattern.

## Alternative Implementation: Divisor Check

This version is more explicit and useful for learning.

```python
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)

        for length in range(1, n // 2 + 1):
            if n % length != 0:
                continue

            pattern = s[:length]
            if pattern * (n // length) == s:
                return True

        return False
```

We only need to check lengths up to `n // 2`, because the repeated substring must appear at least twice.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.repeatedSubstringPattern("abab") is True
    assert s.repeatedSubstringPattern("aba") is False
    assert s.repeatedSubstringPattern("abcabcabcabc") is True
    assert s.repeatedSubstringPattern("a") is False
    assert s.repeatedSubstringPattern("aaaa") is True
    assert s.repeatedSubstringPattern("abac") is False
    assert s.repeatedSubstringPattern("xyzxyz") is True
    assert s.repeatedSubstringPattern("zzzzzz") is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"abab"` | Basic repeated substring |
| `"aba"` | Looks close but fails |
| `"abcabcabcabc"` | Multiple valid repeating units |
| `"a"` | Single character cannot be repeated from a smaller substring |
| `"aaaa"` | One-character repeated unit |
| `"abac"` | No repeated unit |
| `"xyzxyz"` | Repeated unit of length `3` |
| `"zzzzzz"` | Same character repeated many times |