Repeated String Match - Leetcode Solution

The problem statement is as follows:

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such repetition is possible, return -1.

Example:

Input: A = "abcd", B = "cdabcdab" Output: 3 Explanation: After repeating A three times, we get "abcdabcdabcd". B is a substring of it.

Solution:

The problem is fairly simple to solve. We just need to keep repeating string A until B becomes a substring of it. We can do this by concatenating A with itself until the length of the concatenated string is greater than or equal to the length of B. Then we check if B is a substring of the concatenated string. If it is, we return the number of times A has been repeated.

If after repeating A, the length of the concatenated string is still less than the length of B, then it is not possible to obtain B as a substring of repeated A. In this case, we return -1.

Here is the Python code for the solution:

def repeatedStringMatch(A, B):
    rep = -1
    s = ""
    while len(s) < len(B):
        s += A
        rep += 1
        if B in s:
            return rep + 1
    if B in s + A:
        return rep + 2
    return -1

In the above code, we first initialize rep to -1 and s to an empty string. We keep concatenating A to s until len(s) is greater than or equal to len(B).

Once the length condition is satisfied, we check if B is a substring of s. If it is, we return rep + 1, where rep is the number of times A has been repeated.

If B is not a substring of s, we check if it is a substring of s + A. If it is, we return rep + 2, because we need to add one more repetition of A to s to obtain B as a substring.

If B is not a substring of s or s + A, we return -1, because it is not possible to obtain B as a substring of repeated A.

The time complexity of the above algorithm is O(len(B) * (len(A) + len(B))), because we keep concatenating A to s until len(s) is greater than or equal to len(B). The space complexity is O(len(A) + len(B)), because we need to store the concatenated string s.

1