Problem Description

Given two strings, a and b, your task is to find the minimum number of times you need to repeat string a such that string b becomes a substring of the repeated string. If it is not possible for b to be a substring no matter how many times you repeat a, return -1.

Key Constraints:

• You can repeat a as many times as needed (concatenating copies of a together).
• Find the minimum number of repetitions needed.
• If b can never be a substring, return -1.
• Both a and b are non-empty strings consisting of lowercase English letters.

Thought Process

The problem is about finding the smallest number of times we need to repeat a so that b appears somewhere inside the repeated string.

At first glance, a brute-force approach might be to keep repeating a and checking if b is a substring, but this could be inefficient for long strings.

To optimize, we can reason about the minimum necessary repetitions. Since b must fit entirely within the repeated a, the repeated string must at least be as long as b. Sometimes, we might need to repeat a once more to ensure b can "wrap around" the end of one repetition and the start of the next.

So, the core idea is to repeat a just enough times so that the repeated string is at least as long as b, and possibly one or two more times to handle overlaps.

Solution Approach

Let's break down the steps to solve this problem efficiently:

1. Calculate the minimum repeats:
   • Let repeat_count = ceil(len(b) / len(a)). This ensures the repeated string is at least as long as b.
2. Check for substring:
   • Check if b is a substring of a repeated repeat_count times.
   • Sometimes, b might start at the end of one repetition and finish at the start of the next, so also check repeat_count + 1 repetitions.
3. Return the answer:
   • If b is found in either, return the corresponding repeat count.
   • If not, return -1.

This approach is efficient because it only checks the minimal necessary repeated strings, rather than trying all possible repetitions.

Example Walkthrough

Let's walk through an example for clarity.

Example: a = "abcd", b = "cdabcdab"

1. Compute minimum repeats: len(b) = 8, len(a) = 4.
   repeat_count = ceil(8 / 4) = 2
2. Check: "abcd" * 2 = "abcdabcd".
   Is "cdabcdab" a substring of "abcdabcd"? No.
3. Try one more repeat: "abcd" * 3 = "abcdabcdabcd".
   Is "cdabcdab" a substring of "abcdabcdabcd"? Yes, starting at index 2.
4. So, the answer is 3.

Time and Space Complexity

Brute-force approach:

• Repeats a indefinitely and checks for b at each step.
• Time Complexity: Potentially O(N * M) where N is the length of a and M is the length of b.
• Space Complexity: O(N * K) where K is the number of repetitions (could be large).

• Only checks up to repeat_count + 1 repetitions.
• Time Complexity: O(N + M) for string concatenation and substring search (amortized, using efficient substring search algorithms).
• Space Complexity: O(N * K), but K is at most repeat_count + 1, which is small (typically 2 or 3).

The optimization comes from limiting the number of repetitions we check, making the approach efficient even for large inputs.

Summary

The key insight is that you only need to repeat a just enough times to cover the length of b, plus one extra in case b wraps around. By calculating this minimum and checking only these cases, we avoid unnecessary work and solve the problem efficiently. This strategy leverages string properties and careful analysis of overlaps, resulting in a concise and elegant solution.

Code Implementation

import math

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        repeat = math.ceil(len(b) / len(a))
        repeated_a = a * repeat
        if b in repeated_a:
            return repeat
        repeated_a += a
        if b in repeated_a:
            return repeat + 1
        return -1
      

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int repeat = (b.size() + a.size() - 1) / a.size();
        string repeated_a = "";
        for (int i = 0; i < repeat; ++i) {
            repeated_a += a;
        }
        if (repeated_a.find(b) != string::npos)
            return repeat;
        repeated_a += a;
        if (repeated_a.find(b) != string::npos)
            return repeat + 1;
        return -1;
    }
};
      

class Solution {
    public int repeatedStringMatch(String a, String b) {
        int repeat = (int)Math.ceil((double)b.length() / a.length());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < repeat; ++i) {
            sb.append(a);
        }
        if (sb.indexOf(b) != -1)
            return repeat;
        sb.append(a);
        if (sb.indexOf(b) != -1)
            return repeat + 1;
        return -1;
    }
}
      

var repeatedStringMatch = function(a, b) {
    let repeat = Math.ceil(b.length / a.length);
    let repeatedA = a.repeat(repeat);
    if (repeatedA.indexOf(b) !== -1) return repeat;
    repeatedA += a;
    if (repeatedA.indexOf(b) !== -1) return repeat + 1;
    return -1;
};