Repeated String Match solution and explanation
Google
9 more videos on this problem
6 Repeated String Match Code | String MatchingAditya Verma · 13:42 · 24K views
686. Repeated String Match Leetcode Solution | String Matching AlgorithmADITYA PRAKASH · 16:28 · 14K views
Repeated String Match | Problem of the Day 22/09/21 | Siddharth HazraSchool of AI · 24:01 · 9K views
6 Repeated String Match | String MatchingAditya Verma · 22:37 · 6K views
LeetCode - 686. Repeated String Match | String | JavaOrkhan Gasanov · 6:29 · 3K views
Rolling Hash - LeetCode 686. Repeated String Match Explanation and Solutionhappygirlzt · 18:08 · 2K views
Repeated String Match | 686 Leetcode | C++ | Rabin Karp Algorithm | String MatchingStudy with Tanuja · 12:33 · 1K views
Repeated String Match - Leetcode Problem 686NutShell in a Nutshell · 20:58 · 963 views
686. Repeated String Match (Leetcode Medium)Programming Live with Larry · 21:19 · 459 views
Leetcode 686. Repeated String Match (kmp)LetsCode · 10:11 · 137 views
The problem
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.
def repeatedStringMatch(a: str, b: str) -> int:
m, n = len(a), len(b)
repeat = (n + m - 1) // m
for i in range(repeat + 2):
if b in a * i:
return i
return -1
# Example
print(repeatedStringMatch("abcd", "cdabcdab"))public class Solution {
public int repeatedStringMatch(String a, String b) {
int m = a.length(), n = b.length();
int repeat = (n + m - 1) / m;
StringBuilder sb = new StringBuilder();
for (int i = 0; i <= repeat + 1; i++) {
if (sb.indexOf(b) != -1) return i;
sb.append(a);
}
return -1;
}
public static void main(String[] args) {
Solution solution = new Solution();
String a = "abcd", b = "cdabcdab";
System.out.println(solution.repeatedStringMatch(a, b));
}
}#include <iostream>
#include <string>
int repeatedStringMatch(std::string a, std::string b) {
int m = a.size(), n = b.size();
int repeat = (n + m - 1) / m;
std::string result;
for (int i = 0; i <= repeat + 1; ++i) {
if (result.find(b) != std::string::npos) return i;
result += a;
}
return -1;
}
int main() {
std::string a = "abcd";
std::string b = "cdabcdab";
std::cout << repeatedStringMatch(a, b) << std::endl;
return 0;
}function repeatedStringMatch(a, b) {
const m = a.length, n = b.length;
const repeat = Math.ceil(n / m);
let repeatedA = '';
for (let i = 0; i <= repeat + 1; i++) {
if (repeatedA.includes(b)) return i;
repeatedA += a;
}
return -1;
}
// Example
console.log(repeatedStringMatch("abcd", "cdabcdab"));#include <stdio.h>
#include <string.h>
int repeatedStringMatch(char * a, char * b) {
int m = strlen(a), n = strlen(b);
int repeat = (n + m - 1) / m, i;
char *result = (char *)malloc(m * (repeat + 1) + 1);
result[0] = '\0';
for(i = 0; i < repeat + 1; i++) {
strcat(result, a);
if (strstr(result, b) != NULL) {
free(result);
return i + 1;
}
}
free(result);
return -1;
}
int main() {
char a[] = "abcd";
char b[] = "cdabcdab";
printf("%d\n", repeatedStringMatch(a, b));
return 0;
}using System;
using System.Text;
public class Solution {
public int RepeatedStringMatch(string a, string b) {
int m = a.Length, n = b.Length;
int repeat = (n + m - 1) / m;
StringBuilder sb = new StringBuilder();
for (int i = 0; i <= repeat + 1; i++) {
if (sb.ToString().Contains(b)) return i;
sb.Append(a);
}
return -1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.RepeatedStringMatch("abcd", "cdabcdab"));
}
}In this Python solution, `a` is repeatedly concatenated to make a longer string until either `b` is a substring or the repetition exceeds the possible size necessary to include `b`.
Time Complexity: O((m + n) * n). 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.
def repeatedStringMatch(a: str, b: str) -> int:
m, n = len(a), len(b)
repeat_max = (n + m - 1) // m
doubled = a + a
for i in range(repeat_max + 1):
if b in (doubled[i:] + a):
return i + 1
return -1
print(repeatedStringMatch("abcd", "cdabcdab"))public class Solution {
public int repeatedStringMatch(String a, String b) {
int m = a.length(), n = b.length();
int repeatMax = (n + m - 1) / m;
String doubled = a + a;
for (int i = 0; i < repeatMax; i++) {
if ((doubled + a).substring(i).contains(b)) return i + 1;
}
return -1;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.repeatedStringMatch("abcd", "cdabcdab"));
}
}#include <iostream>
#include <string>
int repeatedStringMatch(std::string a, std::string b) {
int m = a.size(), n = b.size();
int repeat = (n + m - 1) / m;
std::string doubled = a + a;
for (int i = 0; i < repeat; ++i) {
if (doubled.substr(i) + a).find(b) != std::string::npos) return i + 1;
}
return -1;
}
int main() {
std::string a = "abcd";
std::string b = "cdabcdab";
std::cout << repeatedStringMatch(a, b) << std::endl;
return 0;
}function repeatedStringMatch(a, b) {
const m = a.length, n = b.length;
const repeatMax = Math.ceil(n / m);
const doubled = a + a;
for (let i = 0; i <= repeatMax; i++) {
if ((doubled + a).substring(i).includes(b)) return i + 1;
}
return -1;
}
console.log(repeatedStringMatch("abcd", "cdabcdab"));#include <stdio.h>
#include <string.h>
int repeatedStringMatch(char * a, char * b) {
int m = strlen(a), n = strlen(b);
int repeat = (n + m - 1) / m, i;
char *result = (char *)malloc(2 * m + 1);
strcpy(result, a);
strcat(result, a);
for(i = 0; i < repeat; i++) {
if (strstr(result + i * m, b) != NULL) {
free(result);
return i + 1;
}
}
free(result);
return -1;
}
int main() {
char a[] = "abcd";
char b[] = "cdabcdab";
printf("%d\n", repeatedStringMatch(a, b));
return 0;
}using System;
public class Solution {
public int RepeatedStringMatch(string a, string b) {
int m = a.Length, n = b.Length;
int repeatMax = (n + m - 1) / m;
string doubled = a + a;
for (int i = 0; i <= repeatMax; i++) {
if ((doubled + a).Substring(i).Contains(b))
return i + 1;
}
return -1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.RepeatedStringMatch("abcd", "cdabcdab"));
}
}In this Python solution, the functionality takes advantage of a doubled string, examining only necessary segments where b might form entirely using prefix/suffix combinations.
Time Complexity: O(m * n). Space Complexity: O(m).
Approach 3: Default Approach
function repeatedStringMatch(a: string, b: string): number {
const m: number = a.length,
n: number = b.length;
let ans: number = Math.ceil(n / m);
let t: string = a.repeat(ans);
for (let i = 0; i < 3; i++) {
if (t.includes(b)) {
return ans;
}
ans++;
t += a;
}
return -1;
}func repeatedStringMatch(a string, b string) int {
m, n := len(a), len(b)
ans := (n + m - 1) / m
t := strings.Repeat(a, ans)
for i := 0; i < 3; i++ {
if strings.Contains(t, b) {
return ans
}
ans++
t += a
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Repeating String Approach | Time Complexity: O((m + n) * n). Space Complexity: O(m + n). |
| String Matching Optimization with Two Repeats | Time Complexity: O(m * n). Space Complexity: O(m). |
| Default Approach | – |
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. |
Frequently asked questions
Is Repeated String Match easy or hard?
Repeated String Match is rated Medium difficulty. The implementation is simple, but recognizing that only two repetition checks are required requires careful reasoning about string alignment and substring boundaries.
Repeated String Match Python/Java solution
In Python or Java, the typical solution repeats string A until its length reaches or slightly exceeds B, then uses built-in substring search like `in` in Python or `contains()` in Java. The optimized approach checks only k and k+1 repetitions.
How to solve Repeated String Match in O(n)?
Compute the minimum number of repeats needed so the repeated string length is at least len(B). Build A repeated k times and check if B is a substring. If not found, append A once more and check again. These bounded checks keep the algorithm close to linear time.
What is the best approach for Repeated String Match?
The most efficient approach calculates the minimum repetitions needed using k = ceil(len(B) / len(A)), then checks whether B appears in A repeated k or k+1 times. This limits unnecessary string building and runs in roughly O(n + m) time using standard substring search.
Is Repeated String Match asked at Google/Amazon/Meta?
Repeated String Match is a common string manipulation problem frequently seen in technical interviews. Variants involving substring search and repeated patterns have appeared in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Repeated String Match?
The problem primarily uses basic string operations and substring search. No complex data structures are required, but understanding string matching behavior and boundary overlaps between repetitions is key.
What is the time complexity of Repeated String Match?
The optimized solution runs in O(n + m) time where n is the length of A and m is the length of B. Only two substring checks are needed after computing the minimum repetition count. Space complexity is O(n) for the repeated string.