C++ program to remove duplicate characters from string

Question

This is a question in the book "Cracking The Coding Interview".

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.

Follow Up

Write the test cases for this method. The four test cases are

1. String does not contain any duplicates, e.g.: abcd
2. String contains all duplicates, e.g.: aaaa
3. Null string
4. String with all continuous duplicates, e.g.: aaabbb

I want to optimise this code and whether I can use some other function from STL.

#include <iostream>
#include <string>
#include <algorithm>

std::string & removeDuplicate(std::string& str)
{
  int length = str.length();
  for(unsigned int i = 0; i < length; i++)
  {
    char currChar = str[i]; //holds current character
    for(unsigned int j = i+1; j < length; j++)
    {
      if(currChar == str[j])
        str.erase (std::remove(str.begin()+j, str.end(), str[j]), str.end());
    }
  }
  return str;
}

int main()
{
  std::string str;
  std::cout << "Enter string \n";
  std::getline(std::cin, str);
  str = removeDuplicate(str);
  std::cout <<"New String is " << str << "\n";
}

Answer 1

From the tests we are if we are only looking for repeating chars, not duplicate e.g. we can transform "ABBA" into "ABA" (and not "AB"). Then we can use something like:

void removeRepeatingChars(char* s){
  if(!s[0]){                  // Check for enpty string
    return;                   // Notning to do per definition 
  }

  int last=0;                 // Store position of last seen character  thats not a duplicate

  for(int i = 1; s[i] ; i++){ // Loop over all characters and
    if(s[i] != s[last]){      // check if current character is not a dupllicate.
      last++;                 // If so increment the position of last non duplicate and 
      s[last] = s[i];         // copy the currentcharacter to this position.
    }                         // Else go to next char.                            
  }  
  s[++last] = '\0';           // Add string terminator at the end.
}

If not you need to store each seen character and add this check so we get something like.

for(int i = 1; s[i] ; i++){ 
  if(s[i] != s[last] && !sceen[s[i]]){
      last++;
      s[last] = s[i];
      seen[s[i]] = true;
  }
}

Observe that we use that we can modify the string how ever we like on chars we already have checked in order to do the whole operation in place.

Answer 2

As @swerasnym said, it is clear from the test cases that only consecutive duplicates are to be removed. I provide my own solution, despite relying on the same core algorithm, because I think a more modern style is in order:

std::string remove_duplicates(std::string s) {
    if (s.begin() == s.end()) return s;
    auto no_duplicates = s.begin(); 
    for (auto current = no_duplicates; current != s.end();) {
        current = std::find_if(std::next(current), s.end(), [no_duplicates](const char c) { return c != *no_duplicates; });
        *++no_duplicates = std::move(*current);;
    }
    s.erase(++no_duplicates, s.end());
    return s;
}

The differences might appear cosmetic at first, but there are some deeper aspects I'd like to point out:

• Using iterators clearly shows that the core algorithm doesn't rely on the string random-access property, meaning it can be safely generalized to other data structures, like lists.

• I chose to move the duplicate chars, which obviously has no consequence at all. But in a more generic context, if you don't know on what type your algorithm will operate, and if your algorithm doesn't require to preserve the state of an item, prefer a move over a swap or a copy.

• Using std::find_if over a simple by-one incrementation doesn't give you any performance benefit by itself but it states your intent more clearly. Moreover, when the parallel versions of the STL algorithms will become more widely available, you'll be able to make your code faster with a minor change: you'll just have to specify an execution policy.

Answer 3

As you go through the array just record the letters you have seen. So if you have seen them before you can remove them. There are only 26 letters so an array of 26 characters should work. If you want to catch all variations than an array of UCHAR_MAX (all valid characters) can be used (usually around 256 on some rare systems 512 but is directly related to CHAR_BIT).

bool   seen[26] = {0};
std::erase(std::remove_if(std::begin(str), std::end(str), [&seen](unsigned x)
{
    unsigned char lower  = std::to_lower(x);
    bool          result = seen[lower - 'a'];
    seen[lower - 'a']    = true;
    return result;
}));

Answer 4

    int length = str.length();

Whenever you cache results like this, you are telling the reader that calculating the length may be expensive or that the size will not change. That doesn't hold true when you erase elements as you encounter them. The size of the string will shrink with each removal. Without adjusting the size, you'll have access violations when you attempt to read beyond the new, smaller size, if a removal occurred.

---

  for(unsigned int i = 0; i < length; i++) {
    char currChar = str[i]; //holds current character
    for(unsigned int j = i+1; j < length; j++) {
      if(currChar == str[j])
        str.erase (std::remove(str.begin()+j, str.end(), str[j]), str.end());

You seem to have a misunderstanding of how std::remove works. std::remove shifts all values that don't match the value forward. In your code, you remove the duplicates when you encounter the first one, but you keep searching for duplicates (that don't exist) instead of moving on.

---

The standard library provides std::remove_if, which is a function that will remove elements based on a condition. The remove functions are designed to do the looping while you provide it with either a value or predicate.

Poorly-chosen names can mislead the reader and cause bugs. It is important to use descriptive names that match the semantics and role of the underlying entities, within reason. Are you removing elements (shifting elements forward with unspecified elements in the removal area)? Are you erasing elements (removing elements the destructing the unspecified elements)?

auto remove_duplicates(std::string& str) {
  return std::remove_if(str.begin(), str.end(), predicate);
}

std::string& erase_duplicates(std::string& str) {
  str.erase(remove_duplicates(str), str.end());
  return str;
}

As for the predicate, others have suggested using an array lookup scheme, but that violates the "no additional buffer" requirement of the problem. Another way is to keep track of the area that has already been processed as deduplicated (similar to insertion sort working with its processed range).

auto remove_duplicates(std::string& str) {
  auto deduplicated_end = str.begin();
  auto is_duplicate = [&](char ch) {
    auto found = std::find(str.begin(), deduplicated_end, ch) != deduplicated_end;
    if (!found)
      ++deduplicated_end;
    return found;
  };
  return std::remove_if(str.begin(), str.end(), is_duplicate);
}