THE TEAL PICKLE CODING CHALLENGE!! Find the first non repeating character in a string. I solved this problem using bae (C++).
TRY IT 👀 , check out my solution, share!!
Link to problem where you can test against sample cases HERE :)
My solution has an O(n) runtime and uses O(1) additional memory.
Top comments (3)
I'd have thought this would be effective:
That's one linear scan of the portion of the string up to and including the repeated character, plus a search which might be linear, but is more likely constant. While the memory usage varies according to the number of non-repeated characters prior to the first repeated character, it will be relatively efficient. Constant memory doesn't always mean low memory, of course, and the advantage of this construct is that it's trivially templatized for Unicode strings etc.
We can reduce the memory slightly by using a trivial Bloom filter instead:
If you really want to enforce the O(n)/O(1), though, we need to do two things:
1) We won't exit the loop early. That will slow the algorithm down to the level you need.
2) Use a custom allocator to ensure that enough memory for any situation is allocated. This will dramatically increase memory, but allow it to be constant.
The fact both of these make the algorithm demonstrably worse is why I don't like these kinds of artificial constraints...
HI, yay. Awesome attempt at the challenge. Yeah, the constraints are interview based. I tried both of your solutions against sample tests and neither solutions passed.
Feel free to refactor and test against the sample tests ->
Updated the post with the problem link!! (There are sample test cases to test your code!!)