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).
1#include<string>
2using namespace std;
3
4class Solution {
5public:
6 bool repeatedSubstringPattern(string s) {
7 int n = s.size();
8 for (int i = 1; i <= n / 2; ++i) {
9 if (n % i == 0) {
10 string t = s.substr(0, i);
11 bool match = true;
12 for (int j = i; j < n; j += i) {
13 if (s.substr(j, i) != t) {
14 match = false;
15 break;
16 }
17 }
18 if (match) return true;
19 }
20 }
21 return false;
22 }
23};This solution follows a similar logic as Python but capitalizes on C++ STL functions to manage substrings and loop effectively.
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).
1defThe Python solution leverages the find function on a doubled string minus the first and last character to verify presence of original string, thereby inferring repetitive substrings.