Repeated String Match
Problem
Smallest number of times you must repeat a so that b becomes a substring; -1 if impossible.
a='abcd' b='cdabcdab'3def repeated_string_match(a, b):
k = -(-len(b) // len(a)); s = a * k
if b in s: return k
if b in s + a: return k + 1
return -1function repeatedStringMatch(a, b) {
let k = Math.ceil(b.length / a.length); let s = a.repeat(k);
if (s.includes(b)) return k;
if ((s + a).includes(b)) return k + 1;
return -1;
}int repeatedStringMatch(String a, String b) {
int k = (b.length() + a.length() - 1) / a.length();
StringBuilder s = new StringBuilder();
for (int i = 0; i < k; i++) s.append(a);
if (s.toString().contains(b)) return k;
if (s.append(a).toString().contains(b)) return k + 1;
return -1;
}int repeatedStringMatch(string a, string b) {
int k = (b.size() + a.size() - 1) / a.size(); string s;
for (int i = 0; i < k; i++) s += a;
if (s.find(b) != string::npos) return k;
s += a; if (s.find(b) != string::npos) return k + 1;
return -1;
}Explanation
We want the fewest copies of a so that b appears inside the repeated string. The key observation is that we only ever need to check two candidate counts: the smallest number of copies that is at least as long as b, and just one more.
First compute k = ceil(|b| / |a|) with -(-len(b) // len(a)). After k copies, s = a * k is the shortest repeat that could possibly contain b (anything shorter is too short to fit it). If b in s, we are done and return k.
Why try one more? Because b might start partway through one copy and finish partway through another, needing a little extra tail. So if it is not found yet, we check b in s + a (one additional copy) and return k + 1 if it matches. If neither works, b can never be formed from repeats of a, so we return -1.
Example: a = "abcd", b = "cdabcdab" (length 8). k = ceil(8/4) = 2, so s = "abcdabcd" — but b is offset and does not fit. Adding one more copy gives "abcdabcdabcd", which contains "cdabcdab", so the answer is 3.