Testing whether characters of a string are unique

Question

Critiques (even pedantic ones) are welcome.

bool unique_chars(std::string &s) {
    if (s.length()>256) return false;
    std::bitset<256> bs;
    for (auto &c:s) {
        if (bs.test(c)) return false;
        bs.set(c);
    }
    return true;
}

EDIT 1:

for (auto &c:s) {         //OLD
for (unsigned char c:s) { //NEW

Reasoning:

1. char can be either signed or unsigned
2. if signed then bs[] can be out of bounds
3. casting to unsigned eliminates issue as negative values will wrap

EDIT 2:

This string is to be made up of characters from the standard ASCII character set, i.e. fitting into a 1 byte char.

EDIT 3:

Renamed function / added test harness with examples. Function parameter changed to const, as string not being modified.

#include <iostream>
#include <bitset>

bool areCharsUnique(const std::string &s) {
    if (s.length()>256) return false;
    std::bitset<256> bs;
    for (unsigned char c:s) {
        if (bs.test(c)) return false;
        bs.set(c);
    }
    return true;
}

int main() {
    std::string s1 = "hi there";
    std::string s2 = "hey man";
    std::cout << areCharsUnique(s1) << std::endl; //0
    std::cout << areCharsUnique(s2) << std::endl; //1
   return 0;   
}

Answer 1

@Wayne Conrad has made some good points. I just have a few additional ones:

• I'm not sure about checking against a maximum value, but I'll address it anyway.

  In case you'd like to change the default 256, consider having a template parameter. That way, the value can be changed at just one location. It'll also give more meaning to that value.

  template <std::size_t maxChars = 256>
  bool unique_chars(std::string &s) {
      if (s.length() > maxChars) return false;
      std::bitset<maxChars> bs;
  
      // ...
  }
  

• To slightly add on to Wayne's point about const, make sure the argument is const& so that no unnecessary copying is done. In addition, declaring the string argument as const will allow it to be passed in while avoiding casting.

• Consider renaming the function to something like areUniqueChars(). Otherwise, it may sound like it's returning the number of unique chars.

• In C++, prefer to put unary operators (such as & and *) next to the type:

  std::string& s;
  

  for (auto& c : s) {}
  

Answer 2

One theoretical place that this code might fail is when the string contains multibyte characters.

For example UTF-8 encoding is being used and string passed to the function is "€Abبώиב¥£€¢₡₢₣₤₥₦§₧₨₩₪₫₭₮漢Ä©óíßä" although no character is being repeated, the function will return true.

But handling this case is not straight forward at all, as standard library doesn't provide any way to iterate over actual characters in a string.

Answer 3

Critiques (even pedantic ones) are welcome.

There's no 'functional specification' included with your question, there is just the code. You should include a functional specification, a.k.a. "the problem" to be solved, or "the requirements". Without one, we can see what the code does, but cannot assess whether what it does matches what it is required .

If the (missing) functional specification said, "string", then perhaps it doesn't mean only std::string ... for example, it might also mean std::wstring.

If so then your unique_chars should be a template function (in the same way that std::basic_string is a template class).

If you were working with very wide multi-byte characters (e.g. std::char32_t) you would prefer std::set or std::unordered_set (a hash set) instead of a std::bitset.

Answer 4

That's pretty good. It's short. The early returns communicate intent well, and since the function is short, they don't get lost. Formatting is good, and the variable names, although very short, are common abbreveviations that work well here.

I'd consider making the argument const, since it's not modified by the function.

I've been out of C++ a long time, so I might be missing something here, but I'd consider auto c:s instead of auto &c:s. I can't see a reason to work with a reference when a character is cheap to copy.

Answer 5

Here's a two-line solution using some of the standard algorithms: first sort a copy of the string, then use adjacent_find to determine if any adjacent characters are identical. If there aren't, adjacent_find will return the end() iterator of the string copy, so you simply compare against that

bool areCharsUnique(std::string s) 
{
    std::sort(begin(s), end(s));
    return std::adjacent_find(begin(s), end(s)) == end(s);
}

Note that the function takes its argument by-value, which allows also temporaries as arguments. As pointed out by @ChrisW in the comments, you could also use const& as argument but then you would need an extra copy in order to be able to sort.

It works on strings of any length and for any character set.

Live Example.

Answer 6

Good code.

Consider converting a const std::string& parameter into an iterator pair: no reason to not support std::vector<unsigned char>, std::deque-s, etc. You could add a template helper function to have the code run when passed a string s itself, not begin(s), end(s).

On a pedantic note, if you are eager to try fancy things: I would allow non-one-byte inputs, but add an assertions that all the values are in the range [0 .. 256) when unsigned. You could do it using type traits (or by analyzing sizeof(T) at compile time). Basically, if an input is a string/array/container/range of elements of type of sizeof(T) == 1, you need to do nothing else, while if the input is a bunch of int-s, you may want to assert or throw an exception what/if any of the input "characters" is outside this range.