Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
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
This comment is hidden because it contains spoiler information about the solution
Hi there! I wasn't being serious when I wrote comments for my code. I really liked the kata and I was just playing around. I completely agree that the solution you propose is more efficient than my code. I do not agree that the predefined function is effectively two random bit generators; it generates only one bit of entropy. That's why all solutions call the one_two() function twice. (Except me, I call it sixteen times :p ). It would still make more sense if one_two() just returned 0 or 1.
If you count for each iteration of your loop, your algorithm is
O(N^2)
whereN
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 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.count
for each letter in the input.