To remove the Duplicates from the given string (without sorting it)

Question

The question is asking to remove duplicates from the string, I came up with a solution to remove duplicates but for that, I sorted the string. So I wanted to know is there a way of removing duplicates from a string without sorting the string.

Test Cases : 

"allcbcd" -> "alcbd"

My Code (the one in which string has to be sorted) :

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

using namespace std;

string removeDup(string s)
{
   if (s.length() == 0)
   {
       return "";
   }

   sort(s.begin(), s.end());
   char ch = s[0];
   string ans = removeDup(s.substr(1));

   if (ch == ans[0])
   {
       return ans;
   }

   return (ch + ans);
}

int main()
{
   cout << removeDup("allcbbcd") << endl;

   return 0;
}

I can think of a couple easy inefficient ways. Does it have to be efficient? — Eljay, Sep 27 '21 at 19:29
First thing that comes to my mind is using regex. [Here is a SO solution utilizing regex.](https://stackoverflow.com/questions/4574509/remove-duplicate-chars-using-regex) — Frebreeze, Sep 27 '21 at 19:29
Actually, I want an efficient way, but I would also like to know different ways of solving this problem. @Eljay — Jay1105, Sep 27 '21 at 19:31
Note that because you need to just *return* the string with duplicate characters removed, you can create an auxiliary string and copy over characters from the original one-by-one, as long as they haven't been seen before. Figuring out an efficient way to check if a character has been seen before is up to the reader. — wLui155, Sep 27 '21 at 19:37

score 2 · Answer 1 · answered Sep 27 '21 at 19:37

Make a boolean array of size 256 considering only ASCII values.

Loop over the string and check the ASCII index value of the character in the array. If it is already set to true, then ignore that character. If not, add that character to your resultant string and set the ASCII index value to true in the array.

Finally, print the resultant string.

If you want to make it support for UTF-8 chars, use a map instead of an array.

score 0 · Accepted Answer · answered Sep 27 '21 at 19:33

Here is one way to do it without sorting (or using a recursive loop):

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

using namespace std;

string removeDup(string s)
{
   string::size_type index = 0;
   string::iterator end = s.end();

   while (index < s.size()) {
       end = remove(s.begin()+index+1, end, s[index]);
       ++index;
   } 

   s.erase(end, s.end());
   return s;
}

int main()
{
   cout << removeDup("allcbbcd") << endl;

   return 0;
}

Online Demo

To remove the Duplicates from the given string (without sorting it)

2 Answers2