# 686 Repeated String Match

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

**Note:**\
The length of`A`and`B`will be between 1 and 10000.

**The Idea:** The constraint is that A must contain all the letters for B. In other words A must be a subset of B. See how many times A fits into B, and then add A to itself this amount of times. This ensures that A is as least as large as B, which for starters, must at least be the minimum amount, because B must be contained in A. If B is not contained in this string, check the next addition of A.

**Complexity:** O(|B|) time and space

```python
import math
import copy


class Solution:
    def repeatedStringMatch(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """

        A_cp = copy.deepcopy(A)
        n_fit = math.ceil(len(B) / len(A))
        A *= n_fit
        if B in A: return n_fit
        A += A_cp
        if B in A: return n_fit + 1
        return -1


obj = Solution()
print(obj.repeatedStringMatch('abababaaba', 'aabaaba'))  # 2
print(obj.repeatedStringMatch('abcd', 'cdab'))  # 2
print(obj.repeatedStringMatch('abcd', 'cdabcdab'))  # 3
```