# LeetCode 686: Repeated String Match

## Problem Restatement

We are given two strings `a` and `b`.

We need to repeat string `a` some number of times so that `b` becomes a substring of the repeated string.

Return the minimum number of repetitions needed.

If it is impossible, return `-1`.

For example:

```python
a = "abcd"
b = "cdabcdab"
```

Repeating `a` two times gives:

```text
abcdabcd
```

`b` is not a substring.

Repeating `a` three times gives:

```text
abcdabcdabcd
```

Now `b = "cdabcdab"` appears inside it.

So the answer is:

```python
3
```

The official statement asks for the minimum number of times `a` must be repeated so that `b` is a substring, or `-1` if impossible. It also notes that repeating `"abc"` zero times gives an empty string.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two lowercase strings `a` and `b` |
| Output | Minimum repeat count, or `-1` |
| Constraint | `1 <= a.length, b.length <= 10^4` |
| Matching rule | `b` must be a contiguous substring |

Example function shape:

```python
def repeatedStringMatch(a: str, b: str) -> int:
    ...
```

## Examples

Example 1:

```python
a = "abcd"
b = "cdabcdab"
```

Try two repetitions:

```text
abcdabcd
```

`"cdabcdab"` does not fit fully.

Try three repetitions:

```text
abcdabcdabcd
```

Now:

```text
ab cdabcdab cd
```

So the answer is:

```python
3
```

Example 2:

```python
a = "a"
b = "aa"
```

Repeating `a` twice gives:

```text
aa
```

Answer:

```python
2
```

Example 3:

```python
a = "abc"
b = "wxyz"
```

No repeated form of `"abc"` can contain `"wxyz"` because the needed letters do not appear.

Answer:

```python
-1
```

## First Thought: Keep Repeating Until Found

A simple approach is:

1. Start with an empty string.
2. Keep appending `a`.
3. After each append, check whether `b` is a substring.
4. Stop when found.

But we need a safe stopping point.

We cannot repeat forever.

The key is to find the maximum number of repetitions we ever need to check.

## Key Insight

Let:

| Symbol | Meaning |
|---|---|
| `m` | Length of `a` |
| `n` | Length of `b` |

At minimum, the repeated string must be at least as long as `b`.

So the smallest possible repeat count is:

```text
ceil(n / m)
```

Call this number `count`.

There are only two useful cases to check:

| Repeated string | Why |
|---|---|
| `a * count` | Just long enough to contain `b` |
| `a * (count + 1)` | Handles the case where `b` starts near the end of one copy and spills into the next |

For example:

```python
a = "abcd"
b = "cdabcdab"
```

Here:

```text
len(a) = 4
len(b) = 8
ceil(8 / 4) = 2
```

Two copies are long enough in length:

```text
abcdabcd
```

But `b` starts at index `2`, so it needs characters from a third copy:

```text
abcdabcdabcd
  cdabcdab
```

So we also check one extra copy.

If `b` is not in either `a * count` or `a * (count + 1)`, then it will never appear.

## Algorithm

1. Compute:
   ```python id="evlpj6"
   count = ceil(len(b) / len(a))
   ```
2. Build:
   ```python id="hk4iku"
   repeated = a * count
   ```
3. If `b in repeated`, return `count`.
4. If `b in repeated + a`, return `count + 1`.
5. Return `-1`.

We can compute ceiling division without importing `math`:

```python
count = (len(b) + len(a) - 1) // len(a)
```

## Walkthrough

Consider:

```python
a = "abcd"
b = "cdabcdab"
```

Compute:

```text
count = ceil(8 / 4) = 2
```

Build:

```text
repeated = "abcdabcd"
```

Check:

```python
"cdabcdab" in "abcdabcd"
```

This is false.

Add one more copy:

```text
"abcdabcd" + "abcd" = "abcdabcdabcd"
```

Check:

```python
"cdabcdab" in "abcdabcdabcd"
```

This is true.

Return:

```python
3
```

## Correctness

Let `count = ceil(len(b) / len(a))`.

Any repeated string with fewer than `count` copies of `a` is shorter than `b`, so `b` cannot be its substring.

Therefore, the answer cannot be less than `count`.

Now consider any valid occurrence of `b` inside the infinite repeated string:

```text
aaaaaaaa...
```

where each block is one copy of `a`.

The start position of `b` can be shifted into one copy of `a`, because the repeated string is periodic with period `len(a)`.

So the start position only needs to be considered within the first copy of `a`.

Once `a * count` is long enough to cover `b` from position `0`, adding one more copy is enough to cover any occurrence that starts later inside the first copy.

Thus, if `b` appears at all, it must appear inside either:

```text
a * count
```

or:

```text
a * (count + 1)
```

The algorithm checks both in increasing repeat count order.

If the first check succeeds, `count` is minimal.

If the second check succeeds, `count + 1` is minimal.

If neither succeeds, no valid repetition exists.

Therefore, the algorithm returns the correct minimum repeat count or `-1`.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `m` | Length of `a` |
| `n` | Length of `b` |

The repeated string length is at most:

```text
n + 2m
```

Using Python substring search, the practical behavior is efficient.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + m)` expected/practical | We build and search a string only slightly longer than `b` |
| Space | `O(n + m)` | We store the repeated string |

A stricter analysis depends on the implementation of substring search. Conceptually, this can be solved in linear time with KMP or another linear string-matching algorithm.

## Implementation

```python
class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        count = (len(b) + len(a) - 1) // len(a)

        repeated = a * count

        if b in repeated:
            return count

        if b in repeated + a:
            return count + 1

        return -1
```

## Code Explanation

We compute the minimum number of copies needed to reach the length of `b`:

```python
count = (len(b) + len(a) - 1) // len(a)
```

Then we build that many copies:

```python
repeated = a * count
```

First, check whether this is already enough:

```python
if b in repeated:
    return count
```

If not, check one extra copy:

```python
if b in repeated + a:
    return count + 1
```

The extra copy handles matches that start near the end of one repetition and finish in the next.

If both checks fail:

```python
return -1
```

then no repeated form of `a` can contain `b`.

## Testing

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

    assert s.repeatedStringMatch("abcd", "cdabcdab") == 3
    assert s.repeatedStringMatch("a", "aa") == 2
    assert s.repeatedStringMatch("a", "a") == 1
    assert s.repeatedStringMatch("abc", "wxyz") == -1

    assert s.repeatedStringMatch("abc", "cabcabca") == 4
    assert s.repeatedStringMatch("abc", "abcabc") == 2
    assert s.repeatedStringMatch("abc", "bc") == 2
    assert s.repeatedStringMatch("abab", "baba") == 2

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `"abcd"`, `"cdabcdab"` | `3` | Official example |
| `"a"`, `"aa"` | `2` | Repeating one character |
| `"a"`, `"a"` | `1` | Already contained |
| `"abc"`, `"wxyz"` | `-1` | Impossible letters |
| `"abc"`, `"cabcabca"` | `4` | Starts near the end and needs extra copies |
| `"abc"`, `"abcabc"` | `2` | Exact repeated string |
| `"abc"`, `"bc"` | `2` | Substring starts inside first copy and needs next copy under this check strategy |
| `"abab"`, `"baba"` | `2` | Overlapping periodic match |