DEV Community

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

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

✨ thetealpickle 📱 on April 10, 2019

THE TEAL PICKLE CODING CHALLENGE!! Find the first non repeating character in a string. I solved this problem using bae (C++). TRY IT 👀 , check ...
Read full post
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
✨ thetealpickle 📱 •

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
✨ thetealpickle 📱 •

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