Find the minimum number of times a string must be repeated so that another string becomes a substring of the repeated result.
Repeated String Match
Given two strings a and b, repeat string a some number of times to build a longer string. Your task is to determine the smallest number of repetitions needed so that b appears as a contiguous substring of the repeated string.
If no number of repetitions can make b a substring, return -1.
The repeated string is formed by concatenating copies of a end to end, such as a, aa, aaa, and so on.
Input Format
- Two strings
aandb - Both strings contain lowercase English letters
Output Format
- Return the minimum number of repetitions of
aneeded so thatbis a substring - Return
-1if it is impossible
Constraints
1 <= a.length, b.length- Strings contain only lowercase English letters
- A practical solution should avoid building unnecessarily large strings
Example 1
Input
a = "abcd" b = "cdabcdab"
Output
3
Explanation
abcdabcdabcd contains cdabcdab as a substring, and 3 is the minimum number of repetitions.
Example 2
Input
a = "a" b = "aa"
Output
2
Explanation
Repeating a twice gives aa, which contains b.
Show 1 more example
Example 3
Input
a = "abc" b = "wxyz"
Output
-1
Explanation
No repetition of abc can contain wxyz as a substring.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.