# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/686-repeated-string-match.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.