Repeated String Match: Minimum Repetitions for Substring
LeetCode 686, Repeated String Match, asks you to find the minimum number of times you need to repeat string a so that string b becomes a substring of the repeated result. If it is impossible, return -1.
Examples:
a = "abcd",b = "cdab"returns2(repeating gives"abcdabcd", which contains"cdab")a = "a",b = "aa"returns2a = "abc",b = "cabcabca"returns4
The approach: repeat and check
The core idea is that if b can ever appear inside repeated copies of a, you only need a limited number of repetitions to find out. Here is how to think about it.
Start by repeating a until the repeated string is at least as long as b. Call that count count. At this point, the repeated string has enough characters that b could potentially fit inside it. Check whether b is a substring. If it is, return count.
If not, try one more repetition (count + 1). Why? Because b might straddle the boundary between the last copy of a and the next one. One extra copy covers all possible boundary alignments.
If b still is not found after count + 1 repetitions, it will never be found. Return -1.
The key insight is that you never need more than ceil(len(b) / len(a)) + 1 repetitions. Beyond that, you are just adding duplicate overlap that has already been checked.
The code
def repeatedStringMatch(a: str, b: str) -> int:
count = -(-len(b) // len(a))
repeated = a * count
if b in repeated:
return count
if b in repeated + a:
return count + 1
return -1
The expression -(-len(b) // len(a)) is a ceiling division trick. It computes the smallest integer count such that count * len(a) is at least len(b). This avoids importing math.ceil and works cleanly with integer arithmetic.
Visual walkthrough
Let's trace through the example a = "abcd", b = "cdabcdab" step by step. Watch how each additional repetition extends the string until b appears as a substring.
Example: a = "abcd", b = "cdabcdab"
Step 1: Repeat once (count = 1)
"abcd" has length 4, but b has length 8. The repeated string is too short to contain b. Keep going.
Step 2: Repeat twice (count = 2)
"abcdabcd" has length 8, which matches len(b). But b = "cdabcdab" is not found as a substring. The overlap at the boundary is not enough yet.
Step 3: Repeat three times (count = 3)
"abcdabcdabcd" has length 12. Searching for b = "cdabcdab" finds it starting at index 2. Return 3.
At step 3, the repeated string "abcdabcdabcd" finally contains b = "cdabcdab" starting at index 2. The answer is 3.
Notice how b spans across the boundary of the first and second copy of a, and also into the third copy. This is exactly why we sometimes need that extra repetition beyond the minimum length threshold.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n * m), where n = len(a) and m = len(b) |
| Space | O(n * count), for the repeated string |
The repeated string has length at most len(b) + 2 * len(a), which is O(m + n). The substring search using Python's in operator runs in O(m + n) on average (it uses a variant of Boyer-Moore-Horspool). In the worst case, substring search can take O(n * m), but this is rare with typical inputs.
The space cost comes from constructing the repeated string. You build at most ceil(m / n) + 1 copies of a, giving a string of length O(m + n).
Building blocks
String repetition
Repeating a string a calculated number of times is the foundation of this problem. Python makes it simple with the * operator, but the underlying idea is universal. You are constructing a longer string that has enough room to contain the target. This same concept appears in problems involving cyclic strings, wrap-around matching, and circular buffer simulations.
Substring checking
Once you have built the repeated string, the problem reduces to a single substring search. The in operator handles this, but knowing what it does under the hood matters. Python uses a fast search algorithm internally, so b in repeated is efficient. In other languages, you might use indexOf, find, or contains. The same building block powers problems like Find the Index of the First Occurrence in a String.
Ceiling division
Computing the minimum number of repetitions requires ceiling division: ceil(len(b) / len(a)). The integer arithmetic trick -(-b // a) avoids floating-point issues and is a handy pattern for any problem where you need to round up a division result.
Edge cases
b is longer than a. This is the typical case. You need multiple repetitions, and the formula ceil(len(b) / len(a)) gives you the starting count. The example above (a = "abcd", b = "cdabcdab") falls into this category.
b is exactly a. If b == a, a single repetition is enough. The function returns 1 because b in a is True on the first check.
b cannot be formed. If b contains characters not in a, or if the character ordering in b is incompatible with any cyclic arrangement of a, the function returns -1 after checking both count and count + 1 repetitions.
b is a single character in a. If b = "c" and a = "abcd", one repetition is sufficient. The ceiling division gives ceil(1/4) = 1, and "c" in "abcd" is True.
a is a single character. If a = "a" and b = "aaaa", you need exactly 4 repetitions. The ceiling division gives ceil(4/1) = 4, and "aaaa" in "aaaa" is True.
b wraps around exactly once. If a = "abc" and b = "cab", you need 2 repetitions. "abcabc" contains "cab". The ceiling division gives ceil(3/3) = 1, but the first check fails, so you try count + 1 = 2 and succeed.
From understanding to recall
Reading about this problem gives you the big picture, but the details that trip you up in an interview are the small ones. Why ceiling division and not floor? Why do you check count + 1 instead of just count? What is the exact expression for the ceiling division trick?
These are the kinds of details that fade fast. You understand them perfectly right now, but next week you might hesitate on whether it is count + 1 or count + 2. Spaced repetition solves this by having you reconstruct the solution from scratch at increasing intervals. After a few reps, the ceiling division formula, the two-check structure, and the -1 fallback become second nature.
Related posts
- Find the Index of the First Occurrence in a String - The foundational substring search problem that this problem builds on
- Repeated Substring Pattern - A related string periodicity problem that uses the double-and-search technique
- Longest Common Prefix - Another string comparison problem that tests character-by-character reasoning