This solution has O(n) runtime over the size n of the input, which is good. It still needs a second pass over (part of) the input, though, which could mean all of the input in the worst case (e.g. when there are no non-repeating characters or the first one occurs late in the input). If you're interested in a solution that does not need a second pass through the input, take a look at my solution.
+1 for reminding me of the extremely useful collections.Counter! Surely I would have implemented the counting myself using a regular dict if I had opted for it in my solution.
Seems like your N's is to small to see benefits from Counter. Your solution is O(n^2), so for large N, your solution will be much slower than op's solution (wich is O(n))
In my benchmark function with Counter was much slower (like 10 time slower) then function with str.count. str.count run N times only if first non-repeating char is last char of string. And str.count itself has O(N) only in worst case
If you count for each iteration of your loop, your algorithm is O(N^2) where N is the length of the input string. Using a counter makes one pass over the entire string, then gives you constant time lookups for the loop. You end up using O(N) time and space for this solution.
Just as an aside - if you were to try to build the counter by using repeated calls to str.count, you would be incurring a quadratic time penalty, because you'd have to call str.count for each letter in the input.
I don't know why I cannot edit the example test cases after re-publishing several times. You need to calculate all primes less than 3 million. That is what P[i] <= 3000000 for all i means.
yeah no you have to implement your own
This solution has O(n) runtime over the size n of the input, which is good. It still needs a second pass over (part of) the input, though, which could mean all of the input in the worst case (e.g. when there are no non-repeating characters or the first one occurs late in the input). If you're interested in a solution that does not need a second pass through the input, take a look at my solution.
+1 for reminding me of the extremely useful
collections.Counter! Surely I would have implemented the counting myself using a regulardictif I had opted for it in my solution.Seems like your N's is to small to see benefits from Counter. Your solution is O(n^2), so for large N, your solution will be much slower than op's solution (wich is O(n))
This comment is hidden because it contains spoiler information about the solution
In my benchmark function with Counter was much slower (like 10 time slower) then function with str.count. str.count run N times only if first non-repeating char is last char of string. And str.count itself has O(N) only in worst case
Nice
Fails for (1001)^2
This comment is hidden because it contains spoiler information about the solution
I really do need to work on my knowledge of the prelude functions. I tend to not rely enough on them.
Thanks for taking the time to answer - you've got a good point, I didn't consider that. The difference is going to be well worth the import.
If you count for each iteration of your loop, your algorithm is
O(N^2)whereNis the length of the input string. Using a counter makes one pass over the entire string, then gives you constant time lookups for the loop. You end up usingO(N)time and space for this solution.Just as an aside - if you were to try to build the counter by using repeated calls to
str.count, you would be incurring a quadratic time penalty, because you'd have to callstr.countfor each letter in the input.Is there any particular reason to use Counter over string.count() here?
Description added.
I don't know why I cannot edit the example test cases after re-publishing several times. You need to calculate all primes less than 3 million. That is what P[i] <= 3000000 for all i means.
Loading more items...