Repeated String Match
Find the minimum number of times string a must be repeated so that b becomes a substring of it, by checking only the two repeat counts that can possibly work.
Problem Understanding
Repeated String Match: return the minimum number of times a must be repeated so that b is a substring of the result, or -1 if that is impossible.
Examples: a = "abcd", b = "cdabcdab" → 3; a = "a", b = "aa" → 2.
The Intuition: b Must Start in the First Copy
All copies of a are identical, so a match can always be slid back to start inside the first copy. That bounds how far it can reach:
- q copies are the fewest that are as long as
b. - Starting in the first copy,
bcan run at most one copy past those q. - So check q and q + 1, and stop.
The same "wrap-around" reasoning shows up in Rotate Array, and matching one string inside another is the job of Find All Anagrams in a String style windows.
Interactive Walkthrough
ALTERNATE COPIES OF a ARE TINTED
ONE COPY
a × 1
b
copies
1
length
4
answer
:
Start with one copy of "abcd" (length 4); b has length 8
Next
Still shorter than b: add a copy, 2 copies, length 8
a
b
Copies of a alternate shading so you can see the boundaries, and b is drawn under its match. Try Extra copy to see why q + 1 is sometimes needed.
Dry Run Table
Input: a = "abcd", b = "cdabcdab" (length 8).
| Copies | Text | Contains b? |
|---|---|---|
| 1 | abcd | too short |
| 2 | abcdabcd | no (length 8, but b starts at index 2) |
| 3 | abcdabcdabcd | yes, at index 2 |
Answer: 3.
The Solution Template
Compute q directly, then two substring checks.
Repeated String Match Code
1var repeatedStringMatch = function(a, b) {2 const copies = Math.ceil(b.length / a.length);3 const text = a.repeat(copies);4 if (text.includes(b)) return copies;5 if ((text + a).includes(b)) return copies + 1;6 return -1;7};
Edge Cases & Common Mistakes
- b shorter than a: q = 1, but b may need 2 copies (a = "ab", b = "ba").
- Looping until a limit: works but wastes time; two checks are enough.
- Only checking q: misses matches that start late in the first copy.
- Character not in a: the answer is -1.
- Integer ceil:
(|b| + |a| − 1) / |a|in languages without a ceil function.
Summary
Let q be the fewest copies of a at least as long as b; return q or q + 1 if b appears in that many copies, else -1. O(n · (n + m)) with a naive substring search.
More practice: DSA interview questions with answers · patterns cheat sheet