Remove duplicate characters from a string in c++

In this tutorial, we will learn how to remove duplicate characters from a given string using the C++ program. We will learn it in two approaches. The first one is simple and uses brute force approach (just by using a temporary array). And the other one is by using a set from STL. The latter has less time complexity than the former.

Algorithm used:

Suppose the given string is: aaabbbbcccccaaaaa

1. We will begin by traversing the whole original array(a[]) and copy the first character of the original array into our new array(b[]).
2. Then, compare the next character of b[] and a[].
3. If they are not equal, then copy the character into our new array i.e b[]. Increase j by 1 and count also by 1.
4. Count is maintained to determine the size of b[].
5. If they are equal, then do nothing. (because it’s the case of repetition)

Here is the C++ code for removing duplicate characters in a string:

#include<bits/stdc++.h>

using namespace std;

int removeduplicate(char a[], char b[], int lengthofstring) {
  int j = 1;
  int count = 0;
  char temp;
  b[0] = a[0];

  for (int i = 0; i < lengthofstring; i++) {
    if (b[j - 1] != a[i]) {
      b[j] = a[i];
      j++;
      count++;
    }

  }
  return count + 1;
}

int main() {
  char a[100];

  cin.getline(a, 90);
  int len = strlen(a);
  char b[100];

  int countofstring = removeduplicate(a, b, len);

  for (int i = 0; i < countofstring; i++) {
    cout << b[i];
  }
}

 

The input is:

aaabbbbcccccaaaaa

The output is:

abca

Time complexity:o(n)

Auxiliary space:o(n)

Alternative method:

Duplicate characters can also be removed by using a set. Set is a container that only stores unique elements. For example, if a set is already <1,4,5,6> and we insert 4 in it. There will be no change and set will be now <1,4,5,6>. If we insert 3 in it, the set will be <1,3,4,5,6>.

We are going to use this alternative way in C++ to remove duplicate characters from a string with the code example.

This is how a set works. Also, internally the elements of a set are in sorted order. Sets are typically implemented as binary search trees.

Here is the code for it:

#include<bits/stdc++.h>

using namespace std;
void remove(char str[],int n)
{
    set<char> s(str,str+n-1);//create a set excluding '/0'
    //print the contents of set
    for(set<char>::iterator it=s.begin();it!=s.end();it++)
    {
        cout<<*it;
    }
}
int main()
{
    char str[100]={"aaabbbbcccccdddd"};
    int n=strlen(str);
    remove(str,n);

}

The output is:

abcd

Time complexity: o(nlogn)

Auxiliary space: o(n)

Also, refer to:

• C++ code to reverse words in a string
• How to find a substring in a given string using C++