713539. Minimum repeat to make substring
Minimum Repeat to Make Substring
Summary
The problem is to find the minimum number of times a string has to be repeated such that another given string becomes a substring of it. This problem involves pattern searching and manipulation of strings, which are key concepts in computer science.
Detailed Explanation
To solve this problem, we can start by considering the simplest case where the repeat count is 1. In this case, the first string must contain the second string as a substring. If the repeat count is more than 1, we need to consider repeating the first string multiple times until it contains the second string.
Here's a step-by-step approach to solve this problem:
- Initialize a variable
repeatCountto 1. - Repeat the first string
repeatCounttimes and concatenate the repeated strings together. - Check if the concatenated string contains the second string as a substring. If it does, return
repeatCount. - Increment
repeatCountby 1 and repeat steps 2-3 until the concatenated string contains the second string as a substring.
The time complexity of this approach is O(n), where n is the length of the first string. The space complexity is also O(n) due to the repeated strings.
Here's an ASCII art diagram illustrating the repetition process:
a -> aa
aa -> aaa
aaa -> aaaa
...
Optimized Solutions
Java
public int minRepeatTimes(String s1, String s2) {
int repeatCount = 1;
while (!s1.repeat(repeatCount).contains(s2)) {
repeatCount++;
}
return repeatCount;
}