Remove duplicate characters from a string

Question

Example of a C++ function which removes duplicates from a string:

string remove_duplicates(string subject) 
{
  string no_duplicates(""); 

  for(int i = 0; i < (int) subject.length(); i++) {
    bool found = false;

    for(int j = 0; j < (int) no_duplicates.length(); j++) {
      if (no_duplicates[j] == subject[i]) {
        found = true;
        break;
      }
    }

    if (!found) no_duplicates += subject[i];
  }

  return no_duplicates;
}

I often find myself writing the subroutine inside which loops through and checks if something is found, if it is NOT found, I need to execute some action. Another approach would be to check if j == no_duplicates.length(), but this doesn't seem optimum as well.

Any suggestions on how to optimize this?

Answer 1

If you don't need to modify a parameter always use const and try to take references. For your exact problem try to create a simple boolean function, e.g. which checks if a character is already in the string. This simplifies things a lot and improves the readability.

In your case there is fortunately already a function for checking if a char is present, std::string find. You can easily use it, e.g:

std::string remove_duplicates(const std::string& subject) {
    std::string no_duplicates;

    for(std::string::const_iterator it = subject.begin(); it != subject.end(); ++it) {

        if (no_duplicates.find(*it) == std::string::npos) // char not found
            no_duplicates += *it;

  }

  return no_duplicates;
}

Answer 2

In C++11, avoid loops. In addition to what Loki said, avoiding loops would yield the following concise code:

std::string remove_duplicates(std::string const& subject) {
    std::string result;
    char duplicates[std::numeric_limits<char>::max()] = { };

    std::copy_if(begin(subject), end(subject), std::back_inserter(result),
        [&](char c) { return duplicates[c]++ == 0; });

    return result;
}

This advice is not just an arbitrary preference: avoiding loops removes whole classes of potential errors (especially overflows and off-by-one errors) which are fundamentally impossible to make in the above code.

But like Loki’s, this code assumes unsigned characters. Unfortunately, this is far from given; therefore, instead of relying on an implicit conversion between characters and integers, an explicit conversion would be required.

Answer 3

This is a well know problem:
Open up one of Knuths book (I hope you have the set lying around).

Anyway a string is a set of char.
char only has 256 values (assuming 8 bits). So you set up an array of 256 counters (set to zero). Then you just start counting how many of each letter there is. The first element that exceeds 1 means you have duplicates:

bool checkduplicates(string const& subject) 
{
  char no_duplicates[256] = {0}; // initialize counts to zero.

  for(std::size_t i = 0; i < subject.length(); i++)
  {
      // need the static cast to make sure the character
      // is not signed and thus potentially negative.
      std::size_t index = static_cast<unsigned char>(subject[i])
      ++no_duplicates[index];

      if (no_duplicates[index] > 1)
      {   return true;
          // I know this changes the meaning of your code.
          // I am just using it as an example of optimal check-duplicates.
          // It would be easy to convert to your code to use this technique.
      }
  }

  return false;
}

Code review:

The function is called remove duplicates.
But that is not what it does. Use names that reflect the actual action.

string remove_duplicates(string subject) 

Given that the function actually only checks for duplicates I would return a bool as a result (unless the output here is being used for other purposes) and I would pass the parameter by const reference. This prevents a copy (if the compiler is feeling sloppy) but more importantly is an indication that it will not be modified.

Avoid C style casts in C++ code. There is absolutely no need for them. There are a whole set of new C++ casts that are designed to be much more easily seen.

Avoid C++ style casts as much as possible. They are an indication that you are overriding the compiler because it can not do something you want it to do.

  for(int i = 0; i < (int) subject.length(); i++) {

In this case you are using the wrong type and you are just asking the compiler to stop complaining. But this makes code harder to maintain. What happens if a maintainer change types of some variable will the cast still hold true? The compiler will still keep quite about any errors as you have indicated with a cast that you know what you are doing and have told it to shut up.

Use the correct type (or one the compiler will not complain about).

Also prefer pre-increment. It does not make any difference for POD types. But it can and usually does make a difference for class types (potentially container iterators). By using pre-increment your code will still work optimally when the types are changed (and it required no other code changes to keep the code working optimally).

Why are you marking work to be done in one location:

        found = true;
        break;

Then doing the work in another?

    if (!found) no_duplicates += subject[i];

It would be easier to read to move the work to the point where it is needed.

for(int j = 0; j < (int) no_duplicates.length(); j++) {
  if (no_duplicates[j] == subject[i]) {
    no_duplicates += subject[i];
    break;
  }
}