loading...
Cover image for [C++ CODE] First Non Repeating Char in String

[C++ CODE] First Non Repeating Char in String

thetealpickle profile image creator Updated on ・1 min read

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.

Discussion

pic
Editor guide
Collapse
dwd profile image
Dave Cridland

I'd have thought this would be effective:

std::string::value_type firstNonRep(std::string const & s) {
    std::unordered_set<std::string::value_type> chars;
    for (auto c : s) {
        bool ok;
        std::tie(std::ignore, ok) = chars.insert(c);
        if (!ok) return c;
    }
    return '_';
}

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:

std::string::value_type firstNonRep(std::string const & s) {
    unsigned long long bloom;
    std::unordered_set<std::string::value_type> chars;
    for (auto c : s) {
        unsigned long long chk = c + ((c % 13) << 8);
        auto old_bloom = bloom;
        bloom |= chk;
        if (old_bloom != bloom) continue;
        bool ok;
        std::tie(std::ignore, ok) = chars.insert(c);
        if (!ok) return c;
    }
    return '_';
}

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

Collapse
thetealpickle profile image
creator Author

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 ->
app.codesignal.com/interview-pract...

Collapse
thetealpickle profile image
creator Author

Updated the post with the problem link!! (There are sample test cases to test your code!!)