Given two strings A and B. Find minimum number of times A has to be repeated such that B is a Substring of it. If B can never be a substring then return -1.
 
Example 1:
Input:
A = "abcd"
B = "cdabcdab"
Output:
3
Explanation:
Repeating A three times (“abcdabcdabcd”),
B is a substring of it. B is not a substring
of A when it is repeated less than 3 times.
Example 2:
Input:
A = "ab"
B = "cab"
Output :
-1
Explanation:
No matter how many times we repeat A, we can't
get a string such that B is a substring of it.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minRepeats() which takes 2 strings A, and B respectively and returns the minimum number of times A has to be repeated such that B is a substring of it. Return -1 if it's not possible.
Expected Time Complexity: O(|A| * |B|)
Expected Auxiliary Space: O(|B|)
Constraints:
1 ≤ |A|, |B| ≤ 10^{3}
String A and B consists of lower case alphabets

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def minRepeats(self, A, B):

        # code here 

Solutions:
from math import gcd

class Solution:

	def minRepeats(self, A, B):
		times = -(-len(B) // len(A))
		if B in A * times:
			return times
		if B in A * (times + 1):
			return times + 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		n = len(B) // len(A)
		if B in A * n:
			return n
		if B in A * (n + 1):
			return n + 1
		if B in A * (n + 2):
			return n + 2
		return -1


class Solution:

	def minRepeats(self, A, B):
		(temp, c) = ('', 0)
		while len(temp) < len(A) + len(B):
			temp += A
			c += 1
			if B in temp:
				return c
		return -1


class Solution:

	def minRepeats(self, A, B):
		n = len(A)
		m = len(B)
		c = 0
		tmp = ''
		while len(tmp) < m:
			tmp += A
			c += 1
		if B in tmp:
			return c
		tmp += A
		c += 1
		if B in tmp:
			return c
		return -1


class Solution:

	def minRepeats(self, A, B):
		(tmp, ct) = ('', 0)
		while len(tmp) < len(A) + len(B):
			tmp += A
			ct += 1
			if B in tmp:
				return ct
		return -1


class Solution:

	def minRepeats(self, A, B):
		a = ''
		repeat = 0
		while len(a) < len(A) + len(B):
			a += A
			repeat += 1
			if B in a:
				return repeat
		return -1


class Solution:

	def minRepeats(self, A, B):
		count = 0
		st = ''
		while len(st) < len(A) + len(B):
			count += 1
			st += A
			if B in st:
				return count
		return -1


class Solution:

	def minRepeats(self, A, B):
		if len(A) >= len(B):
			if B in A:
				return 1
			A += A
			if B in A:
				return 2
			return -1
		c = 1
		st = A
		while len(A) <= len(B):
			if B in A:
				return c
			A += st
			c += 1
		if B in A:
			return c
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		a = len(A)
		b = len(B)
		for i in range(0, a):
			if A[i:min(a, b + i)] != B[:min(a - i, b)]:
				continue
			cnt = 1
			j = min(a - i, b)
			valid = True
			while j < b:
				if A[:min(a, b - j)] == B[j:min(a + j, b)]:
					cnt += 1
					j += a
				else:
					valid = False
					break
			if valid:
				return cnt
		return -1


class Solution:

	def minRepeats(self, A, B):
		x = set(A)
		if set(A) != set(B):
			return -1
		n = len(B)
		n1 = len(A)
		p = n // n1
		y = A * p
		if y.find(B) != -1:
			return p
		elif (y + A).find(B) != -1:
			return p + 1
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		x = set(A)
		for i in B:
			if i not in x:
				return -1
				break
		n = len(B)
		n1 = len(A)
		p = n // n1
		y = A * p
		if y.find(B) != -1:
			return p
		elif (y + A).find(B) != -1:
			return p + 1
		else:
			return -1


class Solution:

	def minRepeats(self, a, b):
		na = len(a)
		nb = len(b)
		n = nb // na
		if b in a * n:
			return n
		if b in a * (n + 1):
			return n + 1
		if b in a * (n + 2):
			return n + 2
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		count = 1
		temp = A
		while len(A) < len(B):
			A += temp
			count += 1
		if B in A:
			return count
		A += A
		count += 1
		if B in A:
			return count
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		x = A * 10 ** 3
		if B not in x:
			return -1
		else:
			x = A
			c = 1
			while B not in x:
				x += A
				c += 1
		return c


class Solution:

	def minRepeats(self, A, B):
		if A == B:
			return 1
		if len(A) > len(B):
			if B in A:
				return 1
			else:
				return -1
		i = 0
		j = 0
		while i < len(A) and j < len(B):
			if A[i] == B[j]:
				i += 1
				j += 1
			else:
				j = 0
				i += 1
		if j == 0:
			return -1
		i = 0
		ans = 0
		flag = True
		while i < len(A) and j < len(B):
			if A[i] == B[j]:
				i += 1
				j += 1
				if i == len(A) and j != len(B):
					ans += 1
					i = 0
				if i == len(A) and j == len(A):
					flag = False
					ans += 1
			else:
				return -1
		if flag == False:
			return ans
		else:
			return ans + 2


class Solution:

	def minRepeats(self, A, B):
		n = len(A)
		m = len(B)
		count = 0
		for i in range(n):
			if A[i] == B[0]:
				k = i
				count = 1
				for j in range(m):
					if k >= n:
						k = 0
						count += 1
					if A[k] != B[j]:
						break
					k += 1
				else:
					return count
		return -1


class Solution:

	def minRepeats(self, A, B):
		if len(A) > len(B):
			return 2
		a = int(len(B) / len(A))
		if B in A * a:
			return a
		elif B in A * (a + 1):
			return a + 1
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		n = len(B)
		m = len(A)
		count = n // m + 2
		for i in range(1, count):
			if B in A * i:
				return i
		return -1


class Solution:

	def minRepeats(self, A, B):
		rep = A
		count = 1
		while len(rep) < len(B):
			rep += A
			count += 1
		if B in rep:
			return count
		else:
			rep += A
			count += 1
		if B in rep:
			return count
		else:
			return -1
		i


class Solution:

	def minRepeats(self, A, B):
		n1 = len(A)
		n2 = len(B)
		n3 = n1
		C = A
		while n3:
			if C != B[:n3]:
				C = C[1:]
				n3 -= 1
			else:
				break
		count = 1
		while n3 < n2:
			C += A
			n3 += n1
			count += 1
		return count if C[:n2] == B else -1


class Solution:

	def minRepeats(self, A, B):
		S = ''
		c = 0
		while B not in S:
			S += A
			c += 1
			if len(S) >= len(B):
				break
		if B in S:
			return c
		elif B in S + A:
			return c + 1
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		m = len(A)
		n = len(B)
		count = 0
		found = False
		for i in range(m):
			j = i
			k = 0
			count = 1
			while k < n and A[j] == B[k]:
				if k == n - 1:
					found = True
					break
				j = (j + 1) % m
				if j == 0:
					count = count + 1
				k = k + 1
			if found:
				return count
		return -1


class Solution:

	def minRepeats(self, A, B):
		a = set(A)
		b = set(B)
		if b.issubset(a):
			S = ''
			ans = 0
			while len(S) < len(B):
				S += A
				ans += 1
			if B in S:
				return ans
			elif B in S + A:
				return ans + 1
			else:
				return -1
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		i = c = 0
		while True:
			a = A * i
			c = c + 1
			if a.find(B) != -1:
				return c - 1
			if len(a) > len(B):
				return -1
			else:
				i = i + 1


class Solution:

	def minRepeats(self, A, B):
		len_a = len(A)
		len_b = len(B)
		for i in range(len_a):
			if A[i] == B[0]:
				k = i
				cnt = 1
				for j in range(len_b):
					if k >= len_a:
						k = 0
						cnt += 1
					if A[k] != B[j]:
						break
					k += 1
				else:
					return cnt
		return -1


import math

class Solution:

	def minRepeats(self, A, B):
		times = int(math.ceil(len(B) / len(A)))
		new_str = A * times
		if B in new_str:
			return times
		new_str = A * (times + 1)
		if B in new_str:
			return times + 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		parent = str(A)
		ans = 1
		while len(parent) < len(B):
			parent = parent + str(A) + ''
			ans += 1
		if parent.find(B) == -1:
			parent = parent + str(A) + ''
			ans += 1
			if parent.find(B) == -1:
				return -1
		return ans


class Solution:

	def minRepeats(self, A, B):
		count = 0
		b = 0
		new = A
		while len(new) <= len(B) + len(A):
			if B in new:
				return count + 1
			count += 1
			new = new + A
		return -1


class Solution:

	def minRepeats(self, A, B):
		repeat = 0
		backup = A
		if A == B:
			return 1
		while B not in backup and len(backup) < len(B) * 1.5:
			repeat += 1
			backup = A * repeat
		if repeat == 0 or B not in backup:
			repeat = -1
		return repeat


import math

class Solution:

	def minRepeats(self, A, B):
		idx = A.find(B[0])
		if idx == -1:
			return -1
		desired_length = math.ceil((idx + len(B)) / len(A))
		list_ = [A for _ in range(desired_length)]
		new_string = ''.join(list_)
		return desired_length if new_string.find(B) != -1 else -1


class Solution:

	def minRepeats(self, a, b):
		if b in a:
			return 1
		s = a
		count = 1
		while len(s) < 2 * len(b):
			if b in s:
				return count
			else:
				s += a
				count += 1
		else:
			return -1


class Solution:

	def minRepeats(self, a, b):
		s = a
		for elm in a:
			if elm not in b:
				return -1
		i = 0
		j = len(b) - 1
		count = 1
		while len(s) < 2 * len(b):
			if len(s) < len(b):
				s += a
				count += 1
			else:
				temp = s[i:j + 1]
				while j < len(s):
					if temp == b:
						return count
					temp = s[i:j + 1]
					i += 1
					j += 1
				if temp == b:
					return count
				s += a
				count += 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		n1 = len(A)
		n2 = len(B)
		count = 1
		k = 0
		while k < n1:
			i = k
			j = 0
			while B[j] == A[i] and j < n2:
				j += 1
				if j == n2:
					return count
				i += 1
				if i == n1:
					i = 0
					count += 1
			k += 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		possibleStart = [i for i in range(len(A)) if B[0] == A[i]]
		alen = len(A)
		for i in possibleStart:
			start = i
			status = True
			count = 1
			for j in B:
				if start == alen:
					start = 0
					count += 1
				if A[start] != j:
					status = False
					break
				start += 1
			if status:
				return count
		return -1


class Solution:

	def minRepeats(self, A, B):
		re = len(B) // len(A)
		stri = ''
		stri += A * re
		if B in stri:
			return re
		else:
			stri += A
			if B in stri:
				return re + 1
			else:
				return -1


class Solution:

	def issubstring(self, str2, rep):
		if str2 in rep:
			return True
		return False

	def minRepeats(self, A, B):
		ans = 1
		S = A
		while len(S) < len(B):
			S += A
			ans += 1
		if self.issubstring(B, S):
			return ans
		elif self.issubstring(B, S + A):
			return ans + 1
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		matchstr = ''
		repeat = 0
		for e in set(A):
			if e not in B:
				return -1
		while len(matchstr) <= len(B):
			matchstr += A
			repeat += 1
			if B in matchstr:
				return repeat
		return -1


class Solution:

	def minRepeats(self, A, B):
		t = len(B) // len(A) + 3
		count = 0
		ans = ''
		for i in range(t):
			if B in ans:
				return count
			ans += A
			count += 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		max = len(B) / len(A) + 1
		min = 1
		rep = A
		for i in range(int(max)):
			if B in A:
				return min
			A = str(A) + str(rep)
			min += 1
		return -1


class Solution:

	def minRepeats(self, a, b):
		len_a = len(a)
		len_b = len(b)
		for i in range(0, len_a):
			if a[i] == b[0]:
				k = i
				count = 1
				for j in range(0, len_b):
					if k >= len_a:
						k = 0
						count = count + 1
					if a[k] != b[j]:
						break
					k = k + 1
				else:
					return count
		return -1


class Solution:

	def minRepeats(self, A, B):
		if set(A) != set(B):
			return -1
		counter = 1
		newA = A
		while len(newA) < len(B):
			newA += A
			counter += 1
		if B in newA:
			return counter
		else:
			newA += newA
			counter += 1
		if B in newA:
			return counter
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		la = len(A)
		lb = len(B)
		min_repeat = 1
		repeated_a = A
		while len(repeated_a) <= la + lb:
			if B in repeated_a:
				return min_repeat
			repeated_a += A
			min_repeat += 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		arr = []
		for i in range(len(A)):
			if B[0] == A[i]:
				arr.append(i)
		for val in arr:
			i = val
			j = 1
			neq = False
			res = 1
			while j < len(B):
				if (i + 1) % len(A) == 0:
					res += 1
				if A[(i + 1) % len(A)] != B[j]:
					neq = True
					break
				i += 1
				j += 1
			if neq == False:
				return res
		return -1


class Solution:

	def minRepeats(self, A, B):
		for i in B:
			if A.find(i) == -1:
				return -1
		for i in range(1, len(B)):
			if (A * i).find(B) != -1:
				return i
			if len(A * i) >= len(A) + len(B):
				return -1


class Solution:

	def minRepeats(self, A, B):
		if B in A:
			return 1
		set_b = set((c for c in B))
		for c in A:
			if c not in set_b:
				return -1
		min_rep = len(B) // len(A)
		if len(B) % len(A) != 0 or A != B[:len(A)]:
			min_rep += 1
		new_A = A * min_rep
		n = len(new_A)
		if B in new_A:
			return min_rep
		for (ind, c) in enumerate(new_A[::-1]):
			if B[0] == c:
				found = True
				cur_ind = n - 1 - ind
				for c2 in B:
					if c2 != new_A[cur_ind]:
						found = False
						break
					cur_ind = (cur_ind + 1) % (n - 1)
				if found:
					if cur_ind > ind:
						cur_ind = cur_ind - ind
					min_rep += (cur_ind + 1) // len(A) + 1
					return min_rep
		return -1


class Solution:

	def minRepeats(self, A, B):
		ans = len(B) // len(A)
		s = ''
		s += A * ans
		if B in s:
			return ans
		else:
			s += A
			if B in s:
				return ans + 1
			else:
				return -1


class Solution:

	def minRepeats(self, A, B):
		s = A
		moves = 1
		while len(A) < len(B):
			A += s
			moves += 1
		if A.find(B) != -1:
			return moves
		A += s
		moves += 1
		if A.find(B) != -1:
			return moves
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		if len(A) > len(B):
			if B in A:
				return 1
			elif B in A + A:
				return 2
			else:
				return -1
		else:
			ans = 1
			temp = A
			while len(temp) < len(B):
				ans += 1
				temp += A
			if B in temp:
				return ans
			elif B in temp + A:
				return ans + 1
			else:
				return -1


class Solution:

	def minRepeats(self, a, b):
		n = len(a)
		m = len(b)
		tmp = ''
		c = 0
		while len(tmp) < n + m:
			tmp += a
			c += 1
			if b in tmp:
				return c
		return -1


class Solution:

	def minRepeats(self, A, B):
		for i in B:
			if i not in A:
				return -1
		if A == B:
			return 1
		S = A
		c = 1
		if A in B:
			while len(A) < len(B):
				A += S
				c += 1
			if B in A:
				return c
			else:
				A += S
				c += 1
				if B in A:
					return c
		return -1


class Solution:

	def minRepeats(self, A, B):
		str1 = A
		count = 1
		while len(str1) < len(B):
			str1 = str1 + A
			count = count + 1
		if str1.find(B) == -1:
			str1 = str1 + A
			count = count + 1
			if str1.find(B) == -1:
				return -1
		return count


class Solution:

	def minRepeats(self, A, B):
		a = len(A)
		b = len(B)
		for k in range(b):
			if B[k] not in A:
				return -1
		i = 1
		while i < 1000:
			c = A * i
			if B in c:
				return i
			i += 1
		return -1


from math import *

class Solution:

	def minRepeats(self, aa, bb):
		n = len(aa)
		ab = aa
		m = len(bb)
		k = ceil(m / n)
		aa = aa * k
		if bb in aa:
			return k
		else:
			aa += ab
			if bb in aa:
				return k + 1
			else:
				return -1


class Solution:

	def minRepeats(self, A, B):
		ans = 1
		s = A
		while len(s) < len(B):
			s += A
			ans += 1
		if s.__contains__(B):
			return ans
		s += A
		if s.__contains__(B):
			return ans + 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		sup = A
		count = 1
		if B in A:
			return count
		for i in range(len(B) // len(A)):
			sup += A
			count += 1
			if B in sup:
				return count
		return -1


class Solution:

	def minRepeats(self, A, B):
		temp_A = ''
		m = len(B)
		n = len(A)
		repeat_times = m // n + 2
		if B not in A * repeat_times:
			return -1
		cnt = 0
		while True:
			temp_A = temp_A + A
			cnt += 1
			if B in temp_A:
				return cnt


class Solution:

	def minRepeats(self, A, B):
		if set(A) != set(B):
			return -1
		c = 1
		temp = A
		while len(B) > len(A):
			A += temp
			c += 1
		if B not in A:
			A += temp
			c += 1
		if B in A:
			return c
		return -1


class Solution:

	def minRepeats(self, A, B):
		if set(B) != set(A):
			return -1
		min_times = len(B) // len(A)
		for i in range(2):
			_A = A * (min_times + i)
			if _A.find(B) != -1:
				return min_times + i
		return -1


class Solution:

	def minRepeats(self, a, b):
		repeat = 1
		c = a
		while len(b) > len(c):
			c += a
			repeat += 1
		if not b in c:
			c += a
			repeat += 1
		if b in c:
			return repeat
		return -1