# Repeated String Match
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/repeated-string-match)
Canonical: https://scaleengineer.com/dsa/problems/repeated-string-match
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
---
## Problem
Given two strings `a` and `b`, return _the minimum number of times you should repeat string_ `a` _so that string_ `b` _is a substring of it_. If it is impossible for `b`​​​​​​ to be a substring of `a` after repeating it, return `-1`.

**Notice:** string `"abc"` repeated 0 times is `""`, repeated 1 time is `"abc"` and repeated 2 times is `"abcabc"`.

**Example 1:**

**Input:** a = "abcd", b = "cdabcdab"
**Output:** 3
**Explanation:** We return 3 because by repeating a three times "ab**cdabcdab**cd", b is a substring of it.

**Example 2:**

**Input:** a = "a", b = "aa"
**Output:** 2

**Constraints:**

* `1 <= a.length, b.length <= 104`
* `a` and `b` consist of lowercase English letters.

# Approaches
## Simple Iteration with String Matching
This approach directly simulates the process described in the problem. We start with string `a` and keep appending copies of `a` to it until the resulting string is long enough to potentially contain `b`. The key is to realize that we don't need to loop indefinitely. If `b` is a substring of a repeated `a`, it must be found within a string formed by repeating `a` just enough times for its length to be at least `b.length()`, or that same string with one more `a` appended to handle cases where `b` wraps around the concatenation point.
**Time:** O((m + n) * m), where `m` is the length of `b` and `n` is the length of `a`. The `StringBuilder` construction takes O(m+n). The `contains()` method, in the worst case, takes O(text_length * pattern_length). The text length is O(m+n) and the pattern length is `m`. · **Space:** O(m + n), where `m` is the length of `b` and `n` is the length of `a`. This is for the `StringBuilder`, which grows to a length of approximately `m+n`.
**Pros:** The logic is straightforward and easy to implement.; It correctly handles all cases, including the wrap-around case.
**Cons:** The worst-case time complexity is high due to the substring search (`String.contains()`) on a potentially long string. If the underlying implementation is a naive character-by-character comparison, this can lead to a Time Limit Exceeded error on large inputs.
### Explanation
We use a `StringBuilder` for efficient string concatenation. We first build a string `S` by repeating `a` until `S`'s length is at least `b`'s length. Let's say this takes `k` repetitions. We then check if `b` is a substring of `S`. If it is, we've found our answer: `k`. If not, there's one more possibility: `b` could be a substring that starts near the end of `S` and finishes in the next block of `a`. For example, if `a = "abcd"` and `b = "cdab"`, `b` is not in `"abcd"`, but it is in `"abcdabcd"`. So, we perform one final check: we append `a` to `S` one more time and check again. If `b` is a substring now, the answer is `k + 1`. If not, it can never be a substring, so we return -1.

```java
class Solution {
    public int repeatedStringMatch(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        while (sb.length() < b.length()) {
            sb.append(a);
            count++;
        }
        
        // Check if b is in the current repeated string
        if (sb.toString().contains(b)) {
            return count;
        }
        
        // Append a one more time to handle wrap-around cases
        sb.append(a);
        if (sb.toString().contains(b)) {
            return count + 1;
        }
        
        return -1;
    }
}
```
### Algorithm
- Initialize a `StringBuilder` `sb` with the string `a` and a counter `count` to 1.
- In a loop, continue appending `a` to `sb` and incrementing `count` until the length of `sb` is greater than or equal to the length of `b`.
- After the loop, let's say `count` is `k`. The string `sb` is `a` repeated `k` times. Check if `b` is a substring of `sb` using `String.contains()`.
- If it is, `k` is the minimum number of repetitions, so return `count`.
- If not, the match might span across the boundary into the next repetition of `a`. Append `a` one more time to `sb`.
- Check if `b` is a substring of the new, longer `sb`.
- If it is, the answer is `count + 1`.
- If it's still not a substring, it's impossible to form `b`. Return -1.

## Efficient Search with Rolling Hash (Rabin-Karp)
This approach optimizes the previous one by replacing the potentially slow substring search with a guaranteed linear-time algorithm. Algorithms like Rabin-Karp (using a rolling hash) or Knuth-Morris-Pratt (KMP) can find a pattern in a text in time proportional to the sum of their lengths, a significant improvement over the naive quadratic approach. While Java's built-in `String.indexOf()` (used by `contains()`) is highly optimized (often using algorithms like Boyer-Moore), relying on a custom implementation of KMP or Rabin-Karp provides a theoretical guarantee of performance.
**Time:** O(m + n), where `m` is the length of `b` and `n` is the length of `a`. Building the string takes O(m+n). An efficient search algorithm like Rabin-Karp or KMP takes O(text_length + pattern_length) = O((m+n) + m) = O(m+n). · **Space:** O(m + n), for the `StringBuilder` which stores the repeated string.
**Pros:** Provides a guaranteed optimal time complexity.; It is very efficient and will pass for all input constraints.
**Cons:** Implementing advanced algorithms like Rabin-Karp or KMP from scratch is more complex and error-prone than using built-in functions.
### Explanation
The strategy is to reduce the time complexity of the search step. We still construct the candidate string `S` by repeating `a` until its length is at least `b`'s length, and then check `S` and `S + a`. However, the check `S.contains(b)` is replaced by a call to a more efficient search function.

A Rabin-Karp implementation would involve choosing a prime modulus and a base for the hash function. It would compute the hash of `b` and then slide a window of length `b.length()` over `S`, updating the hash in O(1) time at each step. This makes the search operation much faster.

For practical purposes, using the built-in `String.indexOf()` in Java is often sufficient as it is heavily optimized. The code would look identical to the first approach, but the justification for its efficiency would rely on the performance of the underlying library implementation rather than a naive search assumption. This approach is about recognizing that the bottleneck is the search and that linear-time solutions exist for it.

```java
class Solution {
    // The code is identical to the simple approach, but we analyze its
    // complexity assuming the underlying .contains()/.indexOf() is optimized
    // to run in linear time, like Rabin-Karp or Boyer-Moore.
    public int repeatedStringMatch(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        while (sb.length() < b.length()) {
            sb.append(a);
            count++;
        }
        
        if (sb.toString().indexOf(b) != -1) {
            return count;
        }
        
        sb.append(a);
        if (sb.toString().indexOf(b) != -1) {
            return count + 1;
        }
        
        return -1;
    }
}
```
### Algorithm
- The overall structure is the same as the simple iterative approach. We build a text string `S` by repeating `a`.
- Instead of using `String.contains()`, we use a more efficient string searching algorithm like Rabin-Karp or Knuth-Morris-Pratt (KMP).
- **Rabin-Karp Logic:**
  1. Calculate the hash of the pattern string `b`.
  2. Build the text string `S` by repeating `a` until `S.length() >= b.length()`. Let this take `k` repetitions.
  3. Use a rolling hash to efficiently calculate the hash of every substring of `S` that has the same length as `b`.
  4. If a substring's hash matches `b`'s hash, perform a direct character comparison to confirm the match (to avoid hash collisions).
  5. If a match is found in `S`, return `k`.
  6. If no match is found, append `a` to `S` and search again in the newly formed string.
  7. If a match is found now, return `k+1`. Otherwise, return -1.

# Solutions
### Java

```java
class Solution { public int repeatedStringMatch ( String a , String b ) { int m = a . length (), n = b . length (); int ans = ( n + m - 1 ) / m ; StringBuilder t = new StringBuilder ( a . repeat ( ans )); for ( int i = 0 ; i < 3 ; ++ i ) { if ( t . toString (). contains ( b )) { return ans ; } ++ ans ; t . append ( a ); } return - 1 ; } }
```

### CPP

```cpp
class Solution { public: int repeatedStringMatch ( string a , string b ) { int m = a . size (), n = b . size (); int ans = ( n + m - 1 ) / m ; string t = "" ; for ( int i = 0 ; i < ans ; ++ i ) t += a ; for ( int i = 0 ; i < 3 ; ++ i ) { if ( t . find ( b ) != - 1 ) return ans ; ++ ans ; t += a ; } return - 1 ; } };
```

### Python

```python
class Solution : def repeatedStringMatch ( self , a : str , b : str ) -> int : m , n = len ( a ), len ( b ) ans = ceil ( n / m ) t = [ a ] * ans for _ in range ( 3 ): if b in '' . join ( t ): return ans ans += 1 t . append ( a ) return - 1
```