Find the Fewest Repetitions Containing a Target String
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the smallest number of repetitions of nonempty a whose concatenation contains b as a contiguous substring. Return -1 if no number of repetitions works.
```cpp
class Solution {
public:
int repeatedStringMatch(string a, string b);
};
```
### Examples
**Example 1:**
```text
a = "xyz", b = "zxyzx"
Output: 3
Explanation: xyzxyzxyz first supplies the target crossing two repetition boundaries.
```
**Example 2:**
```text
a = "ab", b = "ac"
Output: -1
Explanation: Repetition never introduces c.
```
### Constraints
- Both strings contain 1..10000 English lowercase characters.
### Clarifying Questions
Handle repetition-boundary matches and justify a finite impossibility bound.
```hint Read the boundary condition
Can any match starting in a later copy be shifted into the first copy without changing its characters?
```
### Contract considerations
Handle repetition-boundary matches and justify a finite impossibility bound.
Overview: Find the Fewest Repetitions Containing a Target String. Return the smallest number of repetitions of nonempty a whose concatenation contains b as a contiguous substring.
