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 <stdbool.h>
2#include <string.h>
3
4bool repeatedSubstringPattern(char* s) {
5 int n = strlen(s);
6 for (int i = 1; i <= n / 2; ++i) {
7 if (n % i == 0) {
8 bool match = true;
9 for (int j = 0; j < n; ++j) {
10 if (s[j] != s[j % i]) {
11 match = false;
12 break;
13 }
14 }
15 if (match) {
16 return true;
17 }
18 }
19 }
20 return false;
21}The C solution uses nested loops to check feasibility by modular indexing. If a match is not found during comparison, it breaks the loop and continues checking smaller substrings.
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).
1varJavaScript's approach succinctly checks repetition of patterns using slice and includes on a doubled version of the input string.