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.
Quick Steps and Scenarios Overview
| What You Need to Do | Quick Jump |
|---|---|
| Example: | Jump to Step 1 |
| Analysis | Jump to Step 2 |
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()Helpful Tips
Check all labels, connections, and power ratings before starting so everything fits safely and securely. If any detail looks slightly different on your model, pause the embedded video above for a clear closeup view.
Related Guides
- Google 844. Backspace String Compare – Google Interview 844.
- Google Interview Questions – Browse more tutorials and practical guides in this section.






Leave a Reply