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).
1function repeatedStringMatch(a, b) {
2 const m = a.length, n = b.length;
3 const repeat = Math.ceil(n / m);
4 let repeatedA = '';
5 for (let i = 0; i <= repeat + 1; i++) {
6 if (repeatedA.includes(b)) return i;
7 repeatedA += a;
8 }
9 return -1;
10}
11
12// Example
13console.log(repeatedStringMatch("abcd", "cdabcdab"));This JavaScript function repeats string a and checks if b is a substring, incrementing the number of repeats until it finds a match or exhausts logical possibilities.
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
In this Python solution, the functionality takes advantage of a doubled string, examining only necessary segments where b might form entirely using prefix/suffix combinations.