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).
1using System;
2using System.Text;
3
4public class Solution {
5 public int RepeatedStringMatch(string a, string b) {
6 int m = a.Length, n = b.Length;
7 int repeat = (n + m - 1) / m;
8 StringBuilder sb = new StringBuilder();
9 for (int i = 0; i <= repeat + 1; i++) {
10 if (sb.ToString().Contains(b)) return i;
11 sb.Append(a);
12 }
13 return -1;
14 }
15
16 public static void Main(string[] args) {
17 Solution solution = new Solution();
18 Console.WriteLine(solution.RepeatedStringMatch("abcd", "cdabcdab"));
19 }
20}In this C# solution, the code checks for the presence of b within a string, made by appending a incrementally, to see how many concatenations are necessary.
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).
1using System;
public class Solution {
public int RepeatedStringMatch(string a, string b) {
int m = a.Length, n = b.Length;
int repeatMax = (n + m - 1) / m;
string doubled = a + a;
for (int i = 0; i <= repeatMax; i++) {
if ((doubled + a).Substring(i).Contains(b))
return i + 1;
}
return -1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.RepeatedStringMatch("abcd", "cdabcdab"));
}
}This C# code cleverly manages string assembly using a block information strategy, quickly searching a bounded area formed by two repetitions of a.