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.Problem Overview: You are given two strings A and B. The goal is to determine the minimum number of times A must be repeated so that B appears as a substring of the repeated result. If no amount of repetition makes this possible, return -1.
Approach 1: Repeating String Approach (O((n+m) * r) time, O(n * r) space)
This approach directly simulates the process described in the problem. Keep appending A to a growing string until its length becomes at least the length of B. After each repetition, check whether B appears as a substring using standard string search. If it does, return the current repetition count. If not, append A one more time to handle cases where B overlaps across the boundary of two repetitions.
The key insight is that a valid match must appear once the repeated string length reaches or slightly exceeds B. Since substring search itself scans characters sequentially, the total cost depends on both the lengths of the strings and the number of repetitions. This solution relies heavily on basic string operations and built-in substring search.
Approach 2: String Matching Optimization with Two Repeats (O(n + m) time, O(n) space)
This optimization reduces unnecessary repetitions by calculating the minimum base repeats needed before performing substring checks. Compute k = ceil(len(B) / len(A)), which guarantees that the repeated string is at least as long as B. Build the string by repeating A exactly k times and check if B is a substring.
If the match fails, append one more A and check again. At most two checks are required because any valid occurrence of B must either fit entirely inside the first k repetitions or overlap the boundary between repetitions. This keeps the search bounded and avoids building excessively large strings. The method combines reasoning about string lengths with efficient string matching behavior.
Recommended for interviews: The optimized repeat-count approach is what interviewers expect. It shows you understand how substring alignment works across repetition boundaries. Implementing the straightforward repeating approach first demonstrates problem understanding, while limiting the checks to k and k+1 repeats demonstrates algorithmic reasoning and awareness of edge cases.
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.
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.
Time Complexity: O(m * n). Space Complexity: O(m).
Python
Java
C++
Go
TypeScript
| 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). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeating String Approach | O((n+m) * r) | O(n * r) | Simple implementation when directly simulating repeated strings and substring checks. |
| String Matching Optimization with Two Repeats | O(n + m) | O(n) | Preferred interview solution. Limits repetition checks to k and k+1 using string length reasoning. |
6 Repeated String Match Code | String Matching • Aditya Verma • 19,998 views views
Watch 9 more video solutions →Practice Repeated String Match with our built-in code editor and test cases.
Practice on FleetCode