# Share my simple solution

• Try every possible substring, then check.

``````public class Solution {
public boolean repeatedSubstringPattern(String str) {
int len = str.length();
if(len<2) return false;
for(int i=2;i<=len;i++){
if(len%i!=0) continue;
if(check(str, i)) return true;
}
return false;
}
public boolean check(String str, int repeat){
int len = str.length();
String cand = str.substring(0, len/repeat);
for(int i=0;i<len;i++){
if(str.charAt(i)!=cand.charAt(i%(len/repeat))) return false;
}
return true;
}
}
``````

• perfect!perfect code.

• @YuTingLiu

``````int range=(int)Math.sqrt(len);
for(int i=2;i<=range;i++){
if(len%i!=0) continue;
if(check(str, i)) return true;
if(check(str, len/i)) return true;
}
if(check(str, len)) return true;
return false;
``````

Maybe a little bit faster.

• @troy351
i think u r probably wrong, the substring's length could be varied from str.length() / 2 to 1, so there is nothing to do with the sqrt(len)

• @Lara
Let's take `str.length()==16` for example.
original solution:

``````i=2, check 2
i=3, continue
i=4, check 4
i=5, continue
i=6, continue
i=7, continue
i=8, check 8
i=9, continue
i=10, continue
i=11, continue
i=12, continue
i=13, continue
i=14, continue
i=15, continue
i=16, check 16
``````

my solution:

``````i=2, check 2 && check 8
i=3, continue
i=4, check 4 && check 4
check 16
``````

Of course, `sqrt(len)` matters a lot especially when `str.length()` is quite big, like 1 million.

• @troy351 lol
i didn't see u check the original len at the end
thx for explaination

• @YuTingLiu The lower bound of loop `for(int i=0;i<len;i++)` in method `check` seems can have a head start from `len/repeat` instead of `0` since string `cand` itself is a prefix of `str` with length `len/repeat`. Or you could check directly `if(str.substring(len/repeat)) == str.substring(0, len-len/repeat)`.

• @troy351 said in Share my simple solution:

Of course, `sqrt(len)` matters a lot especially when `str.length()` is quite big, like 1 million.

Yes, indeed using `sqrt(len)` as the loop upper bound can reduce time complexity from O(len) + o(len1+e) to O(len0.5) + o(len1+e) for any small e > 0.

• Simpler
public class Solution {
public boolean repeatedSubstringPattern(String str) {
if(str == null || str.length() == 0)
return false;
int pos = (str+str).indexOf(str, 1);
return pos != -1 && pos < str.length();
}
}

• @allen33 brilliant solution

• What is the complexity of this solution?

• @nehad said in Share my simple solution:

What is the complexity of this solution?

I posted a time complexity analysis in my following post:
6-line C++ solution no KMP with detailed time complexity analysis O(n^(1+1/loglog(n))) or o(n^(1+e))

It needs to use the research of the estimated growth rate of number of divisors d(n) if you want a tight complexity estimate.

• It's so cool

• @troy351 Just sharing my opinion.
Your solution is correct, but I don't it's faster in the worst case than the one posted by @YuTingLiu . I think your implementation is slower by `N(sqrt(N) - 1)` character comparisons.

First, I establish this assumption: each `check` take time N: for each `check(str, i)`, we check for each `j = 0..i - 1` that `str.charAt(j)` repeats `len / i - 1` times afterwards, which takes `len / i - 1` character-to-character comparison. Denote `len` by N, we know that each iteration we have to do `i * (len / i - 1)` comparisons. Let's say it's N comparisons each iteration.

Since you are using the `sqrt(N)` here, I take it that we both consent that there are at most `2 * sqrt(N)` divisors for N here.

In your solution, you have `sqrt(N)` iterations, and you do two `check`s in each iteration. The comparisons done in your implementation is gonna be `sqrt(N) * 2 * N`.

In @YuTingLiu 's solution:
There are at most `N` iterations. But there are at most `2sqrt(N)` divisors, so there are at most `2sqrt(N)` iterations where `i` passes the mod test so as to activate the call to `check`. That means only `2sqrt(N)` calls to `check` are made. So the total runtime of her solution is gonna be `N + 2 * sqrt(N) * N`.

You can see that your algorithm actually costs `N * (sqrt(N) - 1)` more time than her solution.

Her solution can actually benefit from a simple optimization: iterate `i` only through `2..N/2`, in this way, her running time would be `N/2 + 2 * sqrt(N) * N`, this is even less.

I tried both codes on the OJ, unfortunately the result is not quite corroborating the analysis: both your version and her version fluctuates between 69ms ~ 88ms across multiple submissions.

There are caveats about this analysis: the analysis above only applies to worst case situations. Since the assumption that each `check` takes N comparisons(it does not terminate prematurely due to mismatch), and the claim that there are at most `2sqrt(N)` divisors for N are both worst case assumptions.

The speed contest might turn out differently in practical cases. If for a particular N, there are actually M divisors for it, then:

• Your solution's # of character comparison: `sqrt(N) + M * 2 * N`
• Her solutions's # of character comparison: `N + M * N`

It is not so likely to prove deterministically the superiority of either solution in this case. Thus you are right that in saying that your solution may be faster.

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