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.In #686 Repeated String Match, 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 becomes a substring of the repeated string. If it is impossible, return -1.
A practical approach is to repeatedly append A until the constructed string length becomes equal to or slightly larger than B. At this point, check whether B appears as a substring. Since the overlap between repetitions may cause B to start near the end of one copy of A and continue into the next, it is often necessary to check one or two additional repetitions.
For substring checking, you can use built-in search methods or more advanced string matching algorithms like KMP (Knuth–Morris–Pratt) for efficiency. The idea is not to generate excessive repetitions but to stop once the repeated string length clearly exceeds what is needed.
The overall complexity typically depends on substring search, giving roughly O(n + m) time with efficient matching and O(n + m) space for the constructed string.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Repeat string + substring search | O(n + m) | O(n + m) |
| Repeat string + KMP string matching | O(n + m) | O(m) |
Abdul Bari
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.
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).
1#include <stdio.h>
2#include <string.h>
3
4int repeatedStringMatch(char * a, char * b) {
5
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.
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.
Time Complexity: O(m * n). Space Complexity: O(m).
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, string manipulation and substring matching problems like Repeated String Match are common in technical interviews. Companies often use them to evaluate understanding of string algorithms, edge cases, and efficient search techniques.
B may start near the end of one repetition of A and continue into the next repetition. Because of this overlap, simply matching lengths may miss valid cases. Adding one or two extra repetitions ensures such cross-boundary matches are detected.
The optimal approach is to keep repeating string A until its length becomes equal to or slightly greater than B, then check if B is a substring. Because overlaps may occur across boundaries, checking one or two additional repetitions is usually sufficient. Efficient substring search like KMP can improve performance.
String matching algorithms such as Knuth–Morris–Pratt (KMP) or built-in substring search functions are commonly used. These methods efficiently detect whether B exists within the repeated string. The key idea is minimizing unnecessary repetitions of A.
Combines two copies of a and then checks
b within different starting indices, thus quickly determining the repetition count.