Given two strings a
and b
, return the minimum number of times you should repeat string a
so that string b
is a substring of it. If it is impossible for b
to be a substring of a
after repeating it, return -1
. For example:
a = "abcd"
, and b = "cdabcdab"
, the answer is 3 because repeating a
three times gives "abcdabcdabcd", and b
is a substring of this.a = "a"
, and b = "aa"
, the answer is 2.Here are some constraints:
a
and b
are between 1 and 10,000.a
and b
consist of lowercase English letters.Describe an algorithm to solve this problem efficiently. What is the time and space complexity of your solution?
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
We're given two strings, call them string A and string B. The brute force approach involves repeatedly writing string A next to itself and then checking if string B appears anywhere within the combined string.
Here's how the algorithm would work step-by-step:
def repeated_string_match_brute_force(string_a, string_b):
repeated_string = ""
repetitions = 0
#Keep appending string_a until string_b is found or it's too large
while len(repeated_string) < len(string_b) + 2 * len(string_a):
repeated_string += string_a
repetitions += 1
#Check if string_b is a substring of the current repeated_string
if string_b in repeated_string:
return repetitions
#If string_b is not found within a reasonable number of repetitions
return -1
The goal is to determine how many times a given string A needs to be repeated so that another string B becomes a substring of the repeated A. We can avoid unnecessary repetitions by first figuring out the absolute minimum number of repetitions needed and then checking only a small range around that minimum.
Here's how the algorithm would work step-by-step:
def repeatedStringMatch(string_a, string_b):
minimum_repetitions = (len(string_b) + len(string_a) - 1) // len(string_a)
repeated_string = string_a * minimum_repetitions
#Check if B is a substring after repeating A
if string_b in repeated_string:
return minimum_repetitions
repeated_string += string_a
#Check if B is a substring after repeating A one more time
if string_b in repeated_string:
return minimum_repetitions + 1
repeated_string += string_a
# B might span across the boundary between repetitions of A
if string_b in repeated_string:
return minimum_repetitions + 2
# If B is still not contained after the second check
return -1
Case | How to Handle |
---|---|
Empty string A or B | If either A or B is empty, return -1 since no repetition of A can contain B. |
String B is much longer than string A | The solution needs to intelligently determine the maximum number of repetitions of A necessary to potentially contain B. |
String A is a very long string | The solution should avoid unnecessary string concatenations which could lead to memory issues or performance degradation. |
String B cannot be formed by repeating A, regardless of how many times A is repeated | The algorithm should detect this case and return -1 efficiently, without entering an infinite loop. |
String A contains string B as a substring | Handle the case where B is already a substring of A to immediately return 1. |
Integer overflow when calculating the number of repetitions | Carefully consider the upper bounds of the number of repetitions to avoid integer overflow issues when calculating the required repetitions of A. |
String A and B are identical | Return 1 since B is already present in A after just one repetition. |
String B consists of characters not present in String A | If B has characters not in A, return -1 after checking character set inclusion |