Repeated String Match: How Many Copies Until b Fits Inside a?
Solve Repeated String Match by repeating string a until b is a substring — with the length limit that proves when to stop, a walkthrough, and JavaScript code.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Repeated String Match looks like a string puzzle but is really a question about when to stop trying. You keep gluing copies of one string together until a second string appears inside it — and the whole difficulty is knowing the exact copy count at which you can safely give up and answer "impossible."
The naive fear is that you might repeat forever. The insight that makes this a clean, terminating algorithm is a tight upper bound on the length: once your repeated string is long enough to cover every possible starting alignment, no further copies can ever help.
Get that bound right and the rest is a three-line loop.
The problem
Given two strings a and b, return the minimum number of times you must repeat a so that b becomes a substring of the result. If b can never be a substring no matter how many times you repeat a, return -1.
Input: a = "abcd", b = "cdabcdab"
Output: 3
// "abcd" + "abcd" + "abcd" = "abcdabcdabcd"
// ^^^^^^^^ b sits at index 2Two things make this trickier than a plain "is b inside a" check:
bcan straddle copy boundaries. In the example,bstarts in copy 1, runs entirely through copy 2, and finishes in copy 3. One copy ofaalone tells you nothing.- The answer can be
-1. Ifbcontains a character that isn't ina, or a cyclic pattern that repeatinganever produces, no number of copies works — and you need a rule that lets you stop searching.
The brute force baseline
The direct simulation is almost the whole solution: keep appending a and checking. The only real question is the stopping condition.
function repeatedStringMatch(a, b) {
let repeated = a;
let count = 1;
// Danger: when does this ever stop?
while (true) {
if (repeated.includes(b)) return count;
repeated += a;
count++;
}
}This returns the right answer when one exists, but it never terminates for impossible cases like a = "abc", b = "wxyz" — it appends forever. A naive fix is to cap count at some arbitrary large number, but that's guesswork. The real fix is a provable length limit.
The key insight: an alignment-based length limit
Think about where b could possibly begin. If b ever appears in the repeated string, its starting position — modulo |a| — is some offset inside a single copy of a. There are only |a| distinct offsets. Once you've built a repeated string long enough that b could start at any of those offsets and still have room to finish, you have tried every alignment there is. Appending more copies just shifts a pattern you've already seen.
That gives a concrete stopping length:
limit = b.length + 2 * a.lengthWhy 2 * a.length of slack? b needs at most ceil(|b| / |a|) copies to hold its own length, plus up to one extra copy because it might start partway through a copy (a partial copy at the front) and end partway through another (a partial copy at the back). Rounding those two partials up to two full copies of a is a safe over-estimate. If b hasn't appeared by the time repeated.length exceeds b.length + 2 * a.length, it never will.
That converts the "run forever" loop into a bounded one.
The optimal solution
Seed repeated with one copy of a, compute the limit once, then append-and-check until you either find b or blow past the limit.
function repeatedStringMatch(a, b) {
let repeated = a;
let count = 1;
let limit = b.length + a.length * 2;
while (repeated.length <= limit) {
if (repeated.includes(b)) {
return count;
}
repeated += a;
count++;
}
return -1;
}The while (repeated.length <= limit) guard is what makes this terminate. Every iteration either returns the current count (success) or grows repeated by one copy of a. Because the answer is checked from the smallest count upward, the first count that satisfies repeated.includes(b) is guaranteed to be the minimum — you never overshoot. If the loop exits without a match, b was unreachable and the function returns -1.
Walkthrough
Trace a = "abcd", b = "cdabcdab". First, limit = 8 + 4 * 2 = 16, and count starts at 1 with repeated = "abcd".
| count | repeated | length | length ≤ 16? | includes("cdabcdab")? | Action |
|---|---|---|---|---|---|
| 1 | abcd | 4 | yes | no | append a → abcdabcd |
| 2 | abcdabcd | 8 | yes | no | append a → abcdabcdabcd |
| 3 | abcdabcdabcd | 12 | yes | yes (at index 2) | return 3 |
At count 3 the repeated string is abcdabcdabcd, and b sits inside it starting at index 2: ab[cdabcdab]cd. The match spans all three copies — it begins two characters into copy 1, runs through copy 2, and ends inside copy 3. That boundary-straddling is exactly why one or two copies weren't enough, and why simulating the growth is the natural way to catch it.
For an impossible input like a = "abc", b = "wxyz", the loop keeps appending until repeated.length exceeds limit = 4 + 6 = 10, then falls through to return -1.
Complexity
Let n = a.length and m = b.length. The repeated string grows to at most m + 2n characters.
| Metric | Big-O | Why |
|---|---|---|
| Time | O((m + n) · m) | The loop runs O((m + n) / n) times; each includes(b) scans a string of length up to m + 2n against b (length m), an O((m + n) · m) substring search overall |
| Space | O(m + n) | repeated holds up to m + 2n characters — the only extra allocation |
In practice the constant is small: at most a couple of extra copies of a beyond what's needed to cover b. The substring search inside includes dominates, which is why the time bound multiplies the built string length by m.
Common mistakes
- No termination guard. Looping
while (true)and appending forever hangs on every impossible input. Therepeated.length <= limitbound is not optional — it's the correctness condition for returning-1. - Setting the limit too low. Using
b.length + a.length(one copy of slack) can miss matches that start late in a copy and finish late in another. You need two copies of headroom, not one. - Starting
countat 0. The answer counts copies, and one copy already exists before the loop. Seedingrepeated = awithcount = 1keeps the two in sync. - Checking with only
ceil(m / n)copies. That length holdsb's characters but ignores offset.bmight need one extra copy purely because it starts partway through the first copy — the classic off-by-one that fails on inputs likea = "abcd",b = "cdabcdab". - Assuming a character check is enough. "Every character of
bis ina" does not imply a match — order and cyclic alignment matter. Only the substring test settles it.
Where this pattern shows up next
Building a string incrementally and testing a property after each step is a recurring string-manipulation move:
- Reverse Words in a String — parsing and rebuilding a string with careful boundary handling.
- Decode String — expanding
k[...]patterns by repeated construction, the encoding cousin of this problem. - Count and Say — generating each term by scanning and rebuilding from the previous one.
- Sum of Beauty of All Substrings — sliding a frequency view across substrings of a built string.
You can also step through Repeated String Match interactively to watch each copy of a get appended and the substring check fire against a growing string.
FAQ
Why do you need two extra copies of a in the length limit?
Because b can start at any offset inside a copy of a and end at any offset inside another. Covering b's own length needs ceil(|b| / |a|) copies, but a match that starts partway through the first copy leaves a partial copy at the front, and a match that ends partway through the last copy leaves a partial copy at the back. Rounding both partials up to full copies of a — hence 2 * a.length of slack — guarantees every possible alignment has been tried before you give up.
When does Repeated String Match return -1?
When b cannot be a substring of any number of repetitions of a. That happens if b contains a character absent from a, or if b's pattern doesn't line up with the cyclic repetition of a. The algorithm proves impossibility by growing the repeated string past b.length + 2 * a.length: once no match has appeared by that length, appending more copies only reproduces alignments already checked, so it safely returns -1.
What is the time complexity of the solution?
O((m + n) · m), where n = a.length and m = b.length. The loop appends copies until the repeated string reaches at most m + 2n characters, running O((m + n) / n) iterations. The cost is dominated by the includes(b) substring search inside the loop, which scans the growing string (length up to m + 2n) against b. Space is O(m + n) for the repeated string itself.
Why not just check if every character of b appears in a?
Because character membership ignores order and alignment. a = "abc" and b = "cab" share all characters, and indeed repeating a to "abcabc" contains "cab" at index 2 — but a character check can't tell you how many copies you need, and it would wrongly pass inputs where the required cyclic order never appears. The substring test on the actual repeated string is the only check that captures both existence and the minimum count.
Does the match ever span more than the copies you'd expect from b's length?
Yes, and that's the whole subtlety. With a = "abcd" and b = "cdabcdab", b is 8 characters and a is 4, so a length-only estimate suggests 2 copies. But b starts at index 2 — two characters into the first copy — so it actually needs 3 copies to finish. The extra copy of headroom in the limit exists precisely to catch matches like this that wrap across one more boundary than their raw length implies.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.