Problem Description

You are given two strings a and b. Your task is to find the minimum number of times you need to repeat string a so that string b becomes a substring of the repeated version of a.

For example:

• If a = "abc" and you repeat it 0 times, you get an empty string ""
• If you repeat it 1 time, you get "abc"
• If you repeat it 2 times, you get "abcabc"
• If you repeat it 3 times, you get "abcabcabc"

The goal is to determine the smallest number of repetitions needed such that b appears as a substring within the repeated a. If it's impossible for b to ever become a substring of repeated a (no matter how many times you repeat), return -1.

The solution works by first calculating the theoretical minimum number of repetitions needed based on the lengths of the strings (ceil(len(b) / len(a))). This gives us the minimum number of copies of a needed to have at least as many characters as b.

Then it checks if b is a substring of the repeated string. If not found initially, it tries adding up to 2 more copies of a to handle cases where b might span across the boundaries of repeated a strings. The algorithm checks at most 3 additional repetitions beyond the theoretical minimum. If b is still not found as a substring after these attempts, it returns -1, indicating it's impossible.

Intuition

To understand why we need to repeat string a, let's think about when b can be a substring of repeated a.

First, we need at least enough characters to cover the length of b. If a = "abc" (length 3) and b = "abcabcab" (length 8), we need at least ceil(8/3) = 3 repetitions of a to have enough characters.

But here's the key insight: even if we have enough characters, b might start in the middle of one copy of a and end in the middle of another copy. For example, if a = "abcd" and b = "cdabcdab", then b starts with "cd" (the tail of one a) and ends with "ab" (the head of another a).

In the worst case, b could:

1. Start near the end of one copy of a
2. Span several complete copies of a in the middle
3. End near the beginning of another copy of a

This means we might need up to 2 extra copies of a beyond the theoretical minimum to account for these boundary cases - one extra for the potential partial match at the beginning and one for the potential partial match at the end.

Therefore, the strategy is:

• Start with the minimum number of repetitions: ceil(len(b) / len(a))
• Check if b is a substring
• If not, try adding one more copy of a (to handle boundary overlaps)
• Keep trying up to 2-3 extra copies
• If b still isn't found, it's impossible

The reason we only need to check a few extra repetitions is that if b isn't found within ceil(len(b) / len(a)) + 2 repetitions, it means b contains some pattern that doesn't exist in any repetition of a, making it impossible.

Solution Approach

The implementation follows a straightforward approach based on our intuition:

1. Calculate the theoretical minimum repetitions:

   m, n = len(a), len(b)
   ans = ceil(n / m)

   We first get the lengths of both strings. The minimum number of repetitions needed is ceil(n / m), which ensures we have at least as many characters as b.

2. Build the initial repeated string:

   t = [a] * ans

   We create a list containing ans copies of string a. Using a list here allows us to efficiently append more copies if needed.

3. Check for substring match with additional attempts:

   for _ in range(3):
       if b in ''.join(t):
           return ans
       ans += 1
       t.append(a)

   We try up to 3 times:

   • First, check if b is a substring of the current repeated string by joining the list t into a single string and using Python's in operator
   • If b is found, return the current count ans
   • If not found, increment ans and append one more copy of a to our list
   • Repeat this process up to 3 times total

4. Return -1 if no match found:

   return -1

   If after checking the minimum required repetitions plus 2 additional copies (3 attempts total), b is still not a substring, it's impossible for b to ever be a substring of repeated a.

The key design choices in this implementation:

• Using a list to store copies of a allows efficient appending
• The in operator provides a clean way to check substring existence
• Limiting to 3 additional attempts is sufficient because if b requires more than ceil(n/m) + 2 repetitions, it contains patterns incompatible with any repetition of a

Example Walkthrough

Let's walk through an example where a = "abcd" and b = "cdabcdab".

Step 1: Calculate theoretical minimum repetitions

• Length of a (m) = 4
• Length of b (n) = 8
• Minimum repetitions = ceil(8/4) = 2
• Initial repeated string: "abcdabcd"

Step 2: Check if b is a substring

• Is "cdabcdab" in "abcdabcd"? No
• The issue: b starts with "cd" which appears at the end of the first a, but we need "cdabcdab" which requires characters from a third copy

Step 3: Add one more copy (attempt 1)

• Repetitions = 3
• New repeated string: "abcdabcdabcd"
• Is "cdabcdab" in "abcdabcdabcd"? Yes!
• Found at position 2: "ab[cdabcdab]cd"

Result: Return 3

This example demonstrates why we need extra copies beyond the theoretical minimum. Even though b has 8 characters and could theoretically fit in 2 copies of a (which gives us 8 characters), the actual substring b spans across boundaries - it starts in the middle of one copy and ends in the middle of another, requiring 3 total copies of a.

Another quick example where it's impossible:

• a = "abc", b = "abac"
• Minimum repetitions = ceil(4/3) = 2 → "abcabc"
• Check: "abac" not in "abcabc" ❌
• Add one more: "abac" not in "abcabcabc" ❌
• Add another: "abac" not in "abcabcabcabc" ❌
• Return -1 (impossible because 'a' never appears after 'b' in any repetition of "abc")

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * (n + m))

The algorithm starts by calculating the minimum number of repetitions needed as ceil(n/m). Then it performs up to 3 additional iterations. In each iteration:

• It joins the list t which contains ans copies of string a, creating a string of length ans * m. This join operation takes O(ans * m) time.
• It checks if b is a substring of the joined string using the in operator, which takes O(ans * m * n) time in the worst case using a naive string matching algorithm.
• Since ans starts at ceil(n/m) and can go up to ceil(n/m) + 2, the maximum length of the concatenated string is approximately (ceil(n/m) + 2) * m, which is O(n + m).
• Therefore, each substring check takes O((n + m) * n) time.
• With at most 3 iterations, the total time complexity is O(n * (n + m)).

Space Complexity: O(n + m)

• The list t stores at most ceil(n/m) + 2 references to string a, but since Python strings are immutable and these are references to the same string object, this takes O(ceil(n/m) + 2) space for the list itself.
• The ''.join(t) operation creates a new string of length at most (ceil(n/m) + 2) * m, which is O(n + m).
• Therefore, the overall space complexity is O(n + m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Checking Too Few Additional Repetitions

One common mistake is only checking the theoretical minimum repetitions without considering edge cases where b might span across boundaries of repeated a strings.

Problem Example:

• a = "abc", b = "cabca"
• Theoretical minimum: ceil(5/3) = 2 → gives us "abcabc"
• But "cabca" is NOT in "abcabc"
• We need 3 repetitions: "abcabcabc" contains "cabca"

Why This Happens: The substring b might start in the middle of one copy of a and end in the middle of another copy. The theoretical minimum only ensures we have enough characters total, not that the pattern aligns correctly.

Solution: Always check at least 2 additional repetitions beyond the theoretical minimum. The current code checks 3 total attempts, which is sufficient because:

• If b requires more than ceil(len(b)/len(a)) + 2 repetitions
• Then b must contain a pattern that can never appear in any repetition of a

2. Inefficient String Concatenation in the Loop

While the current solution works, repeatedly joining strings inside the loop can be inefficient for large strings.

Inefficient Pattern:

for _ in range(3):
    if b in ''.join(t):  # Joining on every iteration
        return ans
    ans += 1
    t.append(a)

Optimized Solution:

# Build the string incrementally
repeated_str = a * min_repetitions
for i in range(3):
    if b in repeated_str:
        return min_repetitions + i
    repeated_str += a

3. Not Handling the Case Where a is Longer Than b

When len(a) > len(b), the theoretical minimum is 1, but developers might incorrectly assume b must be a substring of a single a.

Problem Example:

• a = "abcdef", b = "defabc"
• Theoretical minimum: ceil(6/6) = 1 → gives us "abcdef"
• But "defabc" is NOT in "abcdef"
• We need 2 repetitions: "abcdefabcdef" contains "defabc"

Key Insight: Even when a is longer than b, we might need 2 copies of a if b is formed by the end of one a concatenated with the beginning of another a.