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.
Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".
Example 1:
Input: a = "abcd", b = "cdabcdab" Output: 3 Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.
Example 2:
Input: a = "a", b = "aa" Output: 2
Constraints:
1 <= a.length, b.length <= 104a and b consist of lowercase English letters.This approach involves repeating the string a incrementally and checking if b becomes a substring. The minimum length of repeated a needed should be at least equal to b's length. Thus, start by repeating a just enough times to get a string longer than b and check if b is a substring. If not, repeat a one more time to cover scenarios where b spans two a's boundary.
The solution calculates the number of repetitions needed by dividing n (the length of b) by m (the length of a) rounded up. It creates a new string by repeatedly concatenating a and checks if b is a substring. If not found initially, it adds one more repetition as a final attempt.
C++
Java
Python
C#
JavaScript
Time Complexity: O((m + n) * n), where m is the length of a and n is the length of b. Space Complexity: O(m + n).
This approach relies on two repeated concatenations of string a. As per the pigeonhole principle, if b can fit within the repeated strings, it should certainly fit within two full concatenated repetitions and its prefix or suffix match.
Combines two copies of a and then checks
b within different starting indices, thus quickly determining the repetition count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n). Space Complexity: O(m).
| Approach | Complexity |
|---|---|
| Repeating String Approach | Time Complexity: O((m + n) * n), where |
| String Matching Optimization with Two Repeats | Time Complexity: O(m * n). Space Complexity: O(m). |
9.2 Rabin-Karp String Matching Algorithm • Abdul Bari • 912,392 views views
Watch 9 more video solutions →Practice Repeated String Match with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor