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".
Examples:
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 <= 104
a and b consist of lowercase English letters.
Time Complexity:
Time Complexity = O(m * (m / n)) ≈ O(m² / n)
Space Complexity:
Space Complexity = O(m)
Approach
- Start with
text = aandcount = 1(first repetition). - Since b can only appear when text is at least as long as b, keep appending a to text and
increment count until text.length ≥ b.length. - Once the length condition is met, check if
b exists inside text:- If yes → return count.
- If
not found, append a one more time (this handles cases where b spans across boundaries of repeated a).
- Check again for substring:
If found → return updated count.- If b is still not found, it means
it can never be formed → return -1.
- Minimum repeats = to match
length of b Maximum needed = that + 1(for overlap cases)
Dry Run
Input: a = "abcd", b = "cdabcdab"
Initial:
count = 1
text = "abcd"
While loop (text.length < b.length):
Iteration 1:
text.length = 4 < 8
text = "abcd" + "abcd" = "abcdabcd"
count = 2
Now:
text.length = 8 (not < 8) → exit loop
Check:
"abcdabcd".includes("cdabcdab") → false
Add one more repetition (edge case):
text = "abcdabcd" + "abcd" = "abcdabcdabcd"
count = 3
Check again:
"abcdabcdabcd".includes("cdabcdab") → true
Final:
return 3
Output: 3
var repeatedStringMatch = function(a, b) {
let count = 1;
let text = a;
// Keep appending until length >= b
while (text.length < b.length) {
text += a;
count++;
}
// Check if b is now a substring
if (text.includes(b)) return count;
// One extra append (edge case)
text += a;
count++;
if (text.includes(b)) return count;
return -1;
};
def repeatedStringMatch(a, b):
count = 1
text = a
while len(text) < len(b):
text += a
count += 1
if b in text:
return count
text += a
count += 1
if b in text:
return count
return -1
class Solution {
public int repeatedStringMatch(String a, String b) {
int count = 1;
StringBuilder text = new StringBuilder(a);
while (text.length() < b.length()) {
text.append(a);
count++;
}
if (text.toString().contains(b)) return count;
text.append(a);
count++;
if (text.toString().contains(b)) return count;
return -1;
}
}
class Solution {
public:
int repeatedStringMatch(string a, string b) {
int count = 1;
string text = a;
while (text.length() < b.length()) {
text += a;
count++;
}
if (text.find(b) != string::npos) return count;
text += a;
count++;
if (text.find(b) != string::npos) return count;
return -1;
}
};
#include <stdio.h>
#include <string.h>
int repeatedStringMatch(char* a, char* b) {
static char text[10000]; // assume enough size
strcpy(text, a);
int count = 1;
while (strlen(text) < strlen(b)) {
strcat(text, a);
count++;
}
if (strstr(text, b) != NULL) return count;
strcat(text, a);
count++;
if (strstr(text, b) != NULL) return count;
return -1;
}
public class Solution {
public int RepeatedStringMatch(string a, string b) {
int count = 1;
string text = a;
while (text.Length < b.Length) {
text += a;
count++;
}
if (text.Contains(b)) return count;
text += a;
count++;
if (text.Contains(b)) return count;
return -1;
}
}
