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