Repeated String Match [Medium] — Minimum Repetitions
Sanjeev SharmaAdvertisement
Problem Statement
Given strings a and b, return the minimum number of times a must be repeated so b is a substring. Return -1 if impossible.
Input: a="abcd", b="cdabcdab" → Output: 3
Intuition
We need at least ceil(len(b)/len(a)) repetitions. Try that count and one more. If b is found, return; else -1.
Solutions
C++
int repeatedStringMatch(string a, string b) {
int cnt=1;
string rep=a;
while(rep.size()<b.size()){rep+=a;cnt++;}
if(rep.find(b)!=string::npos) return cnt;
rep+=a;
return (rep.find(b)!=string::npos)?cnt+1:-1;
}
Java
public int repeatedStringMatch(String a, String b) {
int cnt=1;
StringBuilder rep=new StringBuilder(a);
while(rep.length()<b.length()){rep.append(a);cnt++;}
if(rep.indexOf(b)!=-1) return cnt;
rep.append(a);
return rep.indexOf(b)!=-1?cnt+1:-1;
}
Python
def repeatedStringMatch(a: str, b: str) -> int:
import math
cnt = math.ceil(len(b) / len(a))
rep = a * cnt
if b in rep:
return cnt
if b in rep + a:
return cnt + 1
return -1
Complexity
- Time: O((m+n) × n) with naive search; O(m+n) with KMP
- Space: O(m+n)
Advertisement
