Sponsored
Sponsored
This approach involves repeating the string a incrementally and checking if b becomes a substring. The minimum length of repeated a needed should be at least equal to b's length. Thus, start by repeating a just enough times to get a string longer than b and check if b is a substring. If not, repeat a one more time to cover scenarios where b spans two a's boundary.
Time Complexity: O((m + n) * n), where m is the length of a and n is the length of b. Space Complexity: O(m + n).
1def repeatedStringMatch(a: str, b: str) -> int:
2 m, n = len(a), len(b)
3 repeat = (n + m - 1) // m
4 for i in range(repeat + 2):
5 if b in a * i:
6 return i
7 return -1
8
9# Example
10print(repeatedStringMatch("abcd", "cdabcdab"))In this Python solution, `a` is repeatedly concatenated to make a longer string until either `b` is a substring or the repetition exceeds the possible size necessary to include `b`.
This approach relies on two repeated concatenations of string a. As per the pigeonhole principle, if b can fit within the repeated strings, it should certainly fit within two full concatenated repetitions and its prefix or suffix match.
Time Complexity: O(m * n). Space Complexity: O(m).
1#
Combines two copies of a and then checks
b within different starting indices, thus quickly determining the repetition count.