Sponsored
Sponsored
One approach is to take a substring of the given string and repeatedly concatenate to check if it forms the original string. This involves iterating through possible substring lengths and using modular arithmetic to assess potential repeats.
Time Complexity: O(n^2). Space Complexity: O(n).
1public class Solution {
2 public bool RepeatedSubstringPattern(string s) {
3 int n = s.Length;
4 for (int i = 1; i <= n / 2; i++) {
5 if (n % i == 0) {
6 string part = s.Substring(0, i);
7 bool match = true;
8 for (int j = i; j < n; j++) {
9 if (s[j] != part[j % i]) {
10 match = false;
11 break;
12 }
13 }
14 if (match) return true;
15 }
16 }
17 return false;
18 }
19}This C# implementation employs iterating via modulo for in-depth checking while ensuring use of .NET built-in string functions.
Another approach is using the property of doubled strings. By creating a new string by repeating the original and removing the first and last character, we can check if the original string exists within this new string.
Time Complexity: O(n). Space Complexity: O(n).
1#include<string>
using namespace std;
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string ss = s + s;
return ss.substr(1, ss.size() - 2).find(s) != string::npos;
}
};C++ solution utilizes substring and find standard library functions on the concatenated string derived from repeating the string, checking existence.