Repeated String Match - Solution & Explanation
Problem Statement
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 <= 104aandbconsist of lowercase English letters.
Approach Overview
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.
Approach 1: Repeating String Approach
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.
Complexity
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).
Approach 2: String Matching Optimization with Two Repeats
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.
Complexity
Time Complexity: O(m * n). Space Complexity: O(m).
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | ā |
Detailed Complexity Analysis
| 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. |
Video Solution
6 Repeated String Match Code | String Matching ā¢ Aditya Verma ā¢ 24,652 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Repeated String Match easy or hard?
Repeated String Match Python/Java solution
How to solve Repeated String Match in O(n)?
What is the best approach for Repeated String Match?
Is Repeated String Match asked at Google/Amazon/Meta?
What data structure is used in Repeated String Match?
What is the time complexity of Repeated String Match?
Ready to solve this problem?
Practice Repeated String Match with our built-in code editor and test cases.
Practice on FleetCode