# Google Interview 686. Repeated String Match

Google Interview 686. Repeated String Match.

Given two strings a and b, return the minimum number of times you should repeat string a so that string b becomes a subscring of sring a.
If b cannot be a substring of a after repeating it, return -1.

String “acb” repeated 0 times is “”, repeated 1 times is “abc” and 2 times is “abcabc”

## Example:

• Input a= “a”, b= “aa”
• Result 2 because 0=”” 1=”a” 2=”aa”; 2 is the answer here.
• Input a = “a”, b = “a”
• Result is 1 0 = “” 1 = “a”

## Analysis

First check if the strings are the same and return 1
Also check if the string a cannot become a subset of b and return -1.

Repeat string a until string b is a substring.

## Test Code

``````import time
start_time = time.time()
def main():
print("start")

a = "abcd"
b = "cdabcdab"

print ("a: " + a)
print ("b: " + b)

sol = Solution()
result = sol.repeatedStringMatch(a,b)
print("result is: "+ str(result))

print("end")

class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
if not (set(b).issubset(set(a))): return -1
if b in a: return 1

tmp = a
count = 1
for i in range(len(b)//(len(a))+2):
print("-- in loop i: "+ str(i))
print("---- in loop step 1 b: "+ b+ "; tmp: "+ tmp)
if b in tmp:
print("----- in loop FOUND, b: "+ b+ "; tmp: "+ tmp)
return count
tmp += a
count += 1
print("---- in loop step 2 b: "+ b+ "; tmp: "+ tmp)
return -1

if __name__ == "__main__":
main()
print("--- %s ms ---" % int(((time.time() - start_time)*1000)))``````

## Test Output

``````start
a: abcd
b: cdabcdab
-- in loop i: 0
---- in loop step 1 b: cdabcdab; tmp: abcd
---- in loop step 2 b: cdabcdab; tmp: abcdabcd
-- in loop i: 1
---- in loop step 1 b: cdabcdab; tmp: abcdabcd
---- in loop step 2 b: cdabcdab; tmp: abcdabcdabcd
-- in loop i: 2
---- in loop step 1 b: cdabcdab; tmp: abcdabcdabcd
----- in loop FOUND, b: cdabcdab; tmp: abcdabcdabcd
result is: 3
end
>>> ``````

## Final Solution Code

``````def main():
a = "abcd"
b = "cdabcdab"

print ("a: " + a)
print ("b: " + b)

sol = Solution()
result = sol.repeatedStringMatch(a,b)
print("result is: "+ str(result))

class Solution:
def repeatedStringMatch(self, a: str, b: str) -> int:
if not (set(b).issubset(set(a))): return -1
if b in a: return 1

tmp = a
count = 1
while(True):
if b in tmp:
return count
tmp += a
count += 1
return -1

if __name__ == "__main__":
main()``````

Posted

in

by