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 ofAandBwill 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

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