Find the minimum number of times a string must be repeated so that another string becomes a substring of the repeated result.
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.
a and ba needed so that b is a substring-1 if it is impossible1 <= a.length, b.lengthExample 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.
Example 3
Input
a = "abc" b = "wxyz"
Output
-1
Explanation
No repetition of abc can contain wxyz as a substring.
Premium problem context
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.