# My 9 ms C solution with complexity of O(n) (with clear explanation)

• Actually, this is an easy problem. There're just 5 situations we need to take care of.

1. The length of string is 1, just return false
2. The length of string is even or dividable by 3
3. The length of string is even
4. The length of string is dividable by 3
5. The length of string is prime

I defined three functions to solve situation 2, 3, 4 and 5. And the complexity is O(n) at most.
The complete solution is(`the order of these situations matters`):

``````// judge_even(char*, int)
bool judge_even(char* str, int len) {
int i = len / 2;
int j = 0;
while(j < i) {
if(str[j] != str[i+j])
return false;
++j;
}
return true;
}

//judge_db3(char*, int)
bool judge_odd(char* str, int len) {
int i = len / 3;
int j = 2 * i;
int k = 0;
while(k < i) {
if(str[k] != str[i+k] || str[k] != str[j+k])
return false;
++k;
}
return true;
}

//judge_prime(char*, int)
bool judge_prime(char* str, int len) {
char pre = str[0];
int i;
for(i = 1; i < len; ++i) {
if(str[i] != pre)
return false;
pre = str[i];
}
return true;
}

bool repeatedSubstringPattern(char* str) {
int len = strlen(str);

if(1 == len) return false;

if(len % 3 == 0 && len % 2 == 0) {
if(judge_db3(str, len)) return true;
return judge_even(str, len);
/* or
* if(judge_even(str, len)) return true;
* return judge_db3(str, len);
*/
}

if(len % 3 == 0) {
return judge_db3(str, len);
}

if(len % 2 == 0) {
return judge_even(str, len);
}

return judge_prime(str, len);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.