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

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:

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:

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:

The repeated string length is at most:

n + 2m

Using Python substring search, the practical behavior is efficient.

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: