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:
class Solution:

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


class Solution:

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


class Solution:

	def minRepeats(self, A, B):
		i = 0
		count = 1
		s = A
		while i < len(B) / len(A) + 2:
			if s.find(B) != -1:
				return count
			s += A
			count += 1
			i += 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		S = A
		count = 1
		for i in range(400):
			if B in S:
				return count
			else:
				S = S + A
				count += 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		reps = 1
		index_a = len(A) - 1
		index_b = len(B) - 1
		current_a = index_a
		while index_a >= 0:
			while B[index_b] == A[current_a]:
				current_a -= 1
				index_b -= 1
				if index_b < 0:
					return reps
				if current_a < 0:
					current_a = len(A) - 1
					reps += 1
			index_b = len(B) - 1
			index_a -= 1
			current_a = index_a
			reps = 1
		return -1


class Solution:

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


class Solution:

	def minRepeats(self, A, B):
		n = len(B) // len(A) + 1
		start = 0
		end = n + 1
		mid = start + (end - start) // 2
		ans = -1
		while start <= end:
			p = A * mid
			if B in p:
				ans = mid
				end = mid - 1
			else:
				start = mid + 1
			mid = start + (end - start) // 2
		return ans


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(a):
			if A[i:] != B[:min(a - i, b)]:
				continue
			t = 1
			j = min(a - i, b)
			valid = True
			while j < b:
				if B[j:min(j + a, b)] == A[:min(a, b - j)]:
					j += a
					t += 1
				else:
					valid = False
					break
			if valid:
				return t
		return -1


class Solution:

	def minRepeats(self, A, B):
		ai = 0
		bi = 0

		def isEqual(a):
			b = 0
			for _ in range(len(B)):
				if A[a] != B[b]:
					return False
				b += 1
				a = (a + 1) % len(A)
			return True
		start = -1
		for i in range(len(A)):
			if A[i] == B[0]:
				if isEqual(i):
					start = i
					break
		if start == -1:
			return -1
		if start == 0:
			remaining = len(B) - len(A)
		else:
			remaining = len(B) - start + 1
		count = 1
		while remaining > 0:
			count += 1
			remaining -= len(A)
		return count


class Solution:

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


import math

class Solution:

	def minRepeats(self, A, B):
		if B <= A:
			if B in A:
				return 1
			elif B in A + A:
				return 2
			else:
				return -1
		else:
			n = math.ceil(len(B) / len(A))
			S = A * n
			if B in S:
				return n
			elif B in S + A:
				return n + 1
			else:
				return -1


class Solution:

	def minRepeats(self, a, b):
		i = 0
		ans = 1
		while i < len(a):
			f = 0
			if a[i] == b[0]:
				j = i
				k = 0
				while k < len(b):
					if a[j] != b[k]:
						f = 1
						break
					j += 1
					k += 1
					if j == len(a) and k != len(b):
						ans += 1
						j = 0
				if f == 0:
					break
			i += 1
		if f != 0 or i == len(a):
			return -1
		else:
			return ans


class Solution:

	def findSubString(self, A, B):
		a_len = len(A)
		b_len = len(B)
		repeat = b_len - a_len
		if b_len - a_len == 0:
			repeat = 1
		all_done = False
		for i in range(repeat):
			all_done = False
			for j in range(a_len):
				if B[i + j] != A[j]:
					all_done = False
					break
				else:
					all_done = True
			if all_done:
				return True
		return False

	def minRepeats(self, A, B):
		tmp_a = A
		answer = 1
		while len(tmp_a) < len(B):
			tmp_a += A
			answer += 1
		if self.findSubString(B, tmp_a):
			return answer
		if self.findSubString(B, tmp_a + A):
			return answer + 1
		return -1


class Solution:

	def minRepeats(self, a, b):
		x = len(a)
		y = len(b)
		if x > y and b in a:
			return 1
		elif x > y and b in a * 2:
			return 2
		elif x > y:
			return -1
		elif y % x == 0 and b == a * (y // x):
			return y // x
		elif b in a * (y // x + 1):
			return y // x + 1
		else:
			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 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):
		S = A
		ans = 1
		while len(S) < len(B):
			S += A
			ans += 1
		if B in S:
			return ans
		elif B in S + A:
			return ans + 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		dic2 = {}
		for i in range(len(B)):
			if dic2.get(B[i]):
				dic2[B[i]] += 1
			else:
				dic2[B[i]] = 1
		for keyy in dic2.keys():
			if keyy not in A:
				return -1
		i = 0
		j = 0
		n = len(A)
		m = len(B)
		temp = 0
		while temp < n:
			if A[i] != B[0]:
				i = i + 1
			elif A[temp] != B[temp - i]:
				i = i + 1
			temp = temp + 1
		count = 1
		while j < m:
			if A[i] != B[j]:
				return -1
			i = i + 1
			j = j + 1
			if i // n == 1 and j < m:
				count = count + 1
				i = i % n
		return count


class Solution:

	def minRepeats(self, A, B):
		c = 1
		x = A
		while A.find(B) == -1:
			c += 1
			A += x
			if len(A) > len(B) and A.find(B) == -1:
				return -1
		if A.find(B) == -1:
			return -1
		return c


class Solution:

	def minRepeats(self, A, B):
		for i in range(0, len(B)):
			if B[i] not in A:
				return -1
		S = ''
		S = S + A
		c = 1
		if B in S:
			return c
		if B in S + A:
			return c + 1
		f = 0
		while len(S) <= len(B):
			S = S + A
			c = c + 1
			if B in S:
				return c
			elif B in S + A:
				return c + 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		temp = A
		ans = 1
		while len(A) < len(B):
			A += temp
			ans += 1
		if B in A:
			return ans
		A += temp
		ans += 1
		if B in A:
			return ans
		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 += 1
				k += 1
			if found:
				return count
		return -1


class Solution:

	def minRepeats(self, A, B):
		D = A * 10 ** 3
		if B not in D:
			return -1
		count = 1
		C = A
		while B not in A:
			if B in C:
				return count
			C = C + A
			count += 1
		return count


class Solution:

	def minRepeats(self, A, B):
		ans = -1
		for i in range(len(A)):
			j = 0
			tempans = self.Helper(A, B, i, j)
			if tempans != -1:
				return tempans
		return ans

	def Helper(self, A, B, i, j):
		n = len(A)
		count = 0
		flag = False
		while j < len(B):
			while i < len(A) and j < len(B):
				if A[i] == B[j]:
					flag = True
					j += 1
				elif flag:
					return -1
				i += 1
			if flag:
				i = i % n
				count += 1
			else:
				return -1
		if flag:
			return count
		return -1


class Solution:

	def minRepeats(self, A, B):
		i = 0
		s = A
		while B not in s and len(s) < 2 * len(B):
			if B[i] not in A:
				return -1
			s += A
			i += 1
		if B in s:
			return i + 1
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		start_ix = A.find(B[0])
		if start_ix == -1:
			return -1
		ans = 1
		ans += (start_ix + len(B)) // len(A)
		if ans == 1 and B not in A:
			ans += 1
		S = A * ans
		if B in S:
			return ans if S.find(B) + len(B) > len(S) - len(A) else ans - 1
		return -1


from math import ceil

class Solution:

	def minRepeats(self, A, B):
		n = len(A)
		m = len(B)
		org = str(A)
		inc = ceil(m / n)
		A += A * (inc - 1)
		ans = -1
		if B in A:
			ans = inc
		else:
			A += org
			if B in A:
				ans = inc + 1
			else:
				A += org
				if B in A:
					ans = inc + 2
		return ans


class Solution:

	def findChar(self, A, B):
		for b in B:
			if b not in A:
				return False
		else:
			return True

	def minRepeats(self, A, B):
		res = self.findChar(A, B)
		if res:
			i = 1
			temp = A
			l = len(A) + 1
			while A.find(B) == -1:
				A += temp
				i += 1
				if B.find(A[:l]) == -1 and A.find(B) == -1:
					return -1
			return i
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		l1 = len(A)
		l2 = len(B)
		K = 1
		s = A
		while (K - 2) * l1 + 2 <= l2:
			if K * l1 >= l2:
				for i in range(K * l1 - l2 + 1):
					if s[i:i + l2] == B:
						return K
			K += 1
			s += A
		return -1


class Solution:

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


class Solution:

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


class Solution:

	def minRepeats(self, A, B):
		s = ''
		if B in A:
			return 1
		nA = len(A)
		nB = len(B)
		nS = 0
		cnt = 0
		while nS < nB:
			s += A
			nS += nA
			cnt += 1
		if B in s:
			return cnt
		elif B in s + A:
			return cnt + 1
		return -1


class Solution:

	def minRepeats(self, A, B):
		nA = len(A)
		nB = len(B)
		for i in range(nA):
			k = i
			cnt = 1
			isValid = True
			for j in range(nB):
				if A[k] != B[j]:
					isValid = False
				k = (k + 1) % nA
				if k == 0:
					cnt += 1
			if isValid:
				if k == 0:
					cnt -= 1
				return cnt
		return -1


class Solution:

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


import math

class Solution:

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


class Solution:

	def minRepeats(self, A, B):
		count = 1
		if A == B and len(A) == len(B):
			return count
		elif A == B[0:len(A)]:
			s = str(A)
			while len(A) < len(B):
				A = A + s
				count = count + 1
		elif len(A) > len(B):
			A = A + A
			count = count + 1
		else:
			s = str(A)
			while len(A) <= len(B):
				A = A + s
				count = count + 1
		if B in A:
			return count
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		x = max(len(B) // len(A), len(A) // len(B))
		for i in range(2):
			if B in A * (x + i):
				return x + i
				break
		return -1


class Solution:

	def minRepeats(self, A, B):
		str = A
		num = 1
		while B not in str:
			if len(str) > len(B) and num > 3:
				return -1
			str += A
			num = num + 1
		return num


class Solution:

	def minRepeats(self, A, B):
		i = A.find(B[0])
		j = (i + len(B)) / len(A)
		if B in A * (int(j) + 2):
			if int(j) < j:
				j = int(j + 1)
			else:
				j = int(j)
			if j == 1 and B not in A:
				return j + 1
			return j
		return -1


class Solution:

	def minRepeats(self, A, B):
		ans = -1
		for i in range(len(A)):
			index = i
			found = True
			for j in range(len(B)):
				if A[index % len(A)] != B[j]:
					found = False
					break
				index += 1
			if found:
				ans = index // len(A)
				if len(A) * ans != index:
					ans += 1
				break
		return ans


class Solution:

	def minRepeats(self, A, B):
		x = set(A)
		y = set(B)
		if y.issubset(x):
			z = ''
			res = 0
			while len(z) < len(B):
				z += A
				res += 1
			if B in z:
				return res
			elif B in z + A:
				return res + 1
			else:
				return -1
		else:
			return -1


import math

class Solution:

	def minRepeats(self, A, B):
		reps = []
		startpos = []
		for i in range(len(A)):
			if B[0] == A[i]:
				startpos.append(i)
		for i in startpos:
			flagup = True
			repeat = 0
			for j in range(len(B)):
				if B[j] != A[(i + j) % len(A)]:
					flagup = False
				else:
					repeat = (i + j) // len(A)
			if flagup:
				reps.append(repeat + 1)
		if reps == []:
			return -1
		else:
			return min(reps)


import math

class Solution:

	def minRepeats(self, A, B):
		p = A
		n = len(B) // len(A) + 1
		for i in range(n + 2):
			p += A
		j = 0
		for i in range(len(p)):
			if j == len(B):
				return math.ceil(i / len(A))
			if p[i] == B[j]:
				j += 1
			else:
				j = 1 if p[i] == B[0] else 0
		return -1


class Solution:

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


class Solution:

	def minRepeats(self, A, B):
		count = 1
		if A.find(B) > -1:
			return count
		s = A
		found = False
		while len(s) < 2 * len(B):
			s = s + A
			count += 1
			if s.find(B) != -1:
				found = True
				break
		if found:
			return count
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		n1 = len(A)
		n2 = len(B)
		ans1 = -1
		for k in range(n1):
			i = k
			ans = 0
			for j in range(n2):
				if i == 0:
					ans += 1
				if A[i] != B[j]:
					ans = -1
					break
				i += 1
				i %= n1
			ans1 = max(ans1, ans)
		if ans1 != -1 and B.find(A) != 0:
			ans1 += 1
		return ans1


class Solution:

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


class Solution:

	def minRepeats(self, A, B):
		(n, m) = (len(A), len(B))
		start = None
		for i in range(n):
			if A[i] == B[0]:
				new = len(A[i:])
				if A[i:] == B[:new]:
					start = new
					break
		if start == None:
			return -1
		if start == m:
			return 1
		ans = 1
		while m - start >= n:
			if B[start:start + n] == A:
				start = start + n
				ans += 1
			else:
				return -1
		if 0 < m - start < n:
			if B[start:] == A[:m - start]:
				ans += 1
			else:
				return -1
		return ans


class Solution:

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


class Solution:

	def minRepeats(self, A, B):
		c = 0
		i = 0
		while i < len(B) - len(A):
			if A == B[i:i + len(A)]:
				c += 1
				i = i + len(A) - 1
			i += 1
		if B in A * c:
			return c
		elif B in A + A * c or B in A * c + A:
			return c + 1
		elif B in A + A * c + A:
			return c + 2
		else:
			return -1


class Solution:

	def minRepeats(self, A, B):
		s = set(A)
		for i in B:
			if i not in s:
				return -1
		if len(B) >= len(A):
			n = len(B) // len(A)
			A = A * n
			a = A * (n + 1)
			if B in A:
				return n
			elif B in a:
				return n + 1
			else:
				return -1
		else:
			return 2


class Solution:

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


class Solution:

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


class Solution:

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


import math as mt

class Solution:

	def minRepeats(self, A, B):
		na = len(A)
		nb = len(B)
		mn = mt.ceil(nb / na)
		temp = A * mn
		if temp.find(B) != -1:
			return mn
		temp += A
		mn += 1
		if temp.find(B) != -1:
			return mn
		return -1


class Solution:

	def minRepeats(self, s1, s2):
		k = s1
		c = 1
		while len(s1) < len(s2):
			s1 += k
			c += 1
		if s2 in s1:
			return c
		s1 += k
		c += 1
		if s2 in s1:
			return c
		return -1


class Solution:

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


class Solution:

	def minRepeats(self, A, B):
		original = A
		result = 1
		while len(A) < len(B):
			A += original
			result += 1
		if B in A:
			return result
		A += original
		result += 1
		if B in A:
			return result
		return -1


class Solution:

	def minRepeats(self, a, b):
		st = a
		m = len(b)
		flag = 0
		count = 0
		while len(a) < len(b):
			count += 1
			a += st
		if b in a:
			count += 1
			return count
		else:
			a += st
			count += 1
			if b in a:
				return count + 1
			else:
				return -1