@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 checks 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.