LeetCode 686: Repeated String Match

Problem Restatement

We are given two strings a and b.

We need to repeat string a some number of times so that b becomes a substring of the repeated string.

Return the minimum number of repetitions needed.

If it is impossible, return -1.

For example:

a = "abcd"
b = "cdabcdab"

Repeating a two times gives:

abcdabcd

b is not a substring.

Repeating a three times gives:

abcdabcdabcd

Now b = "cdabcdab" appears inside it.

So the answer is:

3

The official statement asks for the minimum number of times a must be repeated so that b is a substring, or -1 if impossible. It also notes that repeating "abc" zero times gives an empty string.

Input and Output

Item	Meaning
Input	Two lowercase strings a and b
Output	Minimum repeat count, or -1
Constraint	1 <= a.length, b.length <= 10^4
Matching rule	b must be a contiguous substring

Example function shape:

def repeatedStringMatch(a: str, b: str) -> int:
    ...

Examples

Example 1:

a = "abcd"
b = "cdabcdab"

Try two repetitions:

abcdabcd

"cdabcdab" does not fit fully.

Try three repetitions:

abcdabcdabcd

Now:

ab cdabcdab cd

So the answer is:

3

Example 2:

a = "a"
b = "aa"

Repeating a twice gives:

aa

Answer:

2

Example 3:

a = "abc"
b = "wxyz"

No repeated form of "abc" can contain "wxyz" because the needed letters do not appear.

Answer:

-1

First Thought: Keep Repeating Until Found

A simple approach is:

1. Start with an empty string.
2. Keep appending a.
3. After each append, check whether b is a substring.
4. Stop when found.

But we need a safe stopping point.

We cannot repeat forever.

The key is to find the maximum number of repetitions we ever need to check.

Key Insight

Let:

Symbol	Meaning
m	Length of a
n	Length of b

At minimum, the repeated string must be at least as long as b.

So the smallest possible repeat count is:

ceil(n / m)

Call this number count.

There are only two useful cases to check:

Repeated string	Why
a * count	Just long enough to contain b
a * (count + 1)	Handles the case where b starts near the end of one copy and spills into the next

For example:

a = "abcd"
b = "cdabcdab"

Here:

len(a) = 4
len(b) = 8
ceil(8 / 4) = 2

Two copies are long enough in length:

abcdabcd

But b starts at index 2, so it needs characters from a third copy:

abcdabcdabcd
  cdabcdab

So we also check one extra copy.

If b is not in either a * count or a * (count + 1), then it will never appear.

Algorithm

1. Compute:

   count = ceil(len(b) / len(a))
   

2. Build:

   repeated = a * count
   

3. If b in repeated, return count.
4. If b in repeated + a, return count + 1.
5. Return -1.

We can compute ceiling division without importing math:

count = (len(b) + len(a) - 1) // len(a)

Walkthrough

Consider:

a = "abcd"
b = "cdabcdab"

Compute:

count = ceil(8 / 4) = 2

Build:

repeated = "abcdabcd"

Check:

"cdabcdab" in "abcdabcd"

This is false.

Add one more copy:

"abcdabcd" + "abcd" = "abcdabcdabcd"

Check:

"cdabcdab" in "abcdabcdabcd"

This is true.

Return:

3

Correctness

Let count = ceil(len(b) / len(a)).

Any repeated string with fewer than count copies of a is shorter than b, so b cannot be its substring.

Therefore, the answer cannot be less than count.

Now consider any valid occurrence of b inside the infinite repeated string:

aaaaaaaa...

where each block is one copy of a.

The start position of b can be shifted into one copy of a, because the repeated string is periodic with period len(a).

So the start position only needs to be considered within the first copy of a.

Once a * count is long enough to cover b from position 0, adding one more copy is enough to cover any occurrence that starts later inside the first copy.

Thus, if b appears at all, it must appear inside either:

a * count

or:

a * (count + 1)

The algorithm checks both in increasing repeat count order.

If the first check succeeds, count is minimal.

If the second check succeeds, count + 1 is minimal.

If neither succeeds, no valid repetition exists.

Therefore, the algorithm returns the correct minimum repeat count or -1.

Complexity

Let:

Symbol	Meaning
m	Length of a
n	Length of b

The repeated string length is at most:

n + 2m

Using Python substring search, the practical behavior is efficient.

Metric	Value	Why
Time	O(n + m) expected/practical	We build and search a string only slightly longer than b
Space	O(n + m)	We store the repeated string

A stricter analysis depends on the implementation of substring search. Conceptually, this can be solved in linear time with KMP or another linear string-matching algorithm.

Implementation

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        count = (len(b) + len(a) - 1) // len(a)

        repeated = a * count

        if b in repeated:
            return count

        if b in repeated + a:
            return count + 1

        return -1

Code Explanation

We compute the minimum number of copies needed to reach the length of b:

count = (len(b) + len(a) - 1) // len(a)

Then we build that many copies:

repeated = a * count

First, check whether this is already enough:

if b in repeated:
    return count

If not, check one extra copy:

if b in repeated + a:
    return count + 1

The extra copy handles matches that start near the end of one repetition and finish in the next.

If both checks fail:

return -1

then no repeated form of a can contain b.

Testing

def run_tests():
    s = Solution()

    assert s.repeatedStringMatch("abcd", "cdabcdab") == 3
    assert s.repeatedStringMatch("a", "aa") == 2
    assert s.repeatedStringMatch("a", "a") == 1
    assert s.repeatedStringMatch("abc", "wxyz") == -1

    assert s.repeatedStringMatch("abc", "cabcabca") == 4
    assert s.repeatedStringMatch("abc", "abcabc") == 2
    assert s.repeatedStringMatch("abc", "bc") == 2
    assert s.repeatedStringMatch("abab", "baba") == 2

    print("all tests passed")

run_tests()

Test meaning:

Test	Expected	Why
"abcd", "cdabcdab"	3	Official example
"a", "aa"	2	Repeating one character
"a", "a"	1	Already contained
"abc", "wxyz"	-1	Impossible letters
"abc", "cabcabca"	4	Starts near the end and needs extra copies
"abc", "abcabc"	2	Exact repeated string
"abc", "bc"	2	Substring starts inside first copy and needs next copy under this check strategy
"abab", "baba"	2	Overlapping periodic match