Remove duplicates from the string in CPP

Question

I wrote the following code for removing the duplicates from a given string i.e. if ARRUN is the input then the output will be ARUN.

#include <bits/stdc++.h>
using namespace std;
char* removeDuplicates(string &s,int n){
    char arr[n];
    unordered_map<char,int> exists;
    int index = 0;
    for(int i=0;i<n;i++){
        if(exists[s[i]]==0)
        {
            arr[index++] = s[i];
            exists[s[i]]++;
        }
    }
    return arr;
}

//driver code
int main(){
    string str;
    cin >> str;
    cout<<removeDuplicates(str,str.length())<<endl;
    return 0;
}

The code produces no output at all, however, it works fine if I use char arr[] instead of string class.

Answer 1

You can't use char arr[n] without being n constant or constexpr.

You don't need map. set is sufficient.

Note that map and set remove duplicates already, then you can check if any element is inserted or not to get your new string in the same order of the first, as follows

#include<string>
#include<iostream>
#include<unordered_set>

std::string removeDuplicates(const std::string &s){
    std::string arr;
    std::unordered_set<char> exists;

    for(const auto&el:s)
        if(exists.insert(el).second) arr+=el;

    return arr;
}

//driver code
int main(){
    std::string str;
    std::cin >> str;
    std::cout<<removeDuplicates(str)<<std::endl;
    return 0;
}

Answer 2

std::string support removing elements.

#include <iostream>
#include <string>

std::string removeDuplicates(std::string str) {
    for (int i = 0; i < str.size(); i++) {
        while (true) {
            int j = str.find_last_of(str[i]);
            if (i < j) {
                str.erase(j, 1);
            } else {
                break;
            }
        }
    }
    return str;
}

int main() {
    std::cout << removeDuplicates("ARRUN");
    return 0;
}

Answer 3

@Arun Suryan, You pointed out correctly. But you can do it without using vector by using global char array.

Also don't forget to append the newline at the end!

Have a look at the following code:

#include<string>
#include<iostream>
#include<unordered_map>

char* removeDuplicates(std::string &s,int n){

    std::unordered_map<char,int> exists;
    char* arr = (char*)(malloc(n*sizeof(char)));
    int index = 0;
    for(int i=0;i<n;i++){
        if(exists[s[i]]==0)
        {
            arr[index++] = s[i];
            exists[s[i]]++;
        }
    }
    arr[index] = '\n';
    return arr;
}

//driver code
int main(){
    std::string str;
    std::cin >> str;
    std::cout<<removeDuplicates(str,str.length())<<std::endl;
    return 0;
}

Answer 4

If a function declaration looks the following way

char* removeDuplicates(string &s,int n);

then it means that the passed object itself will be changed in the function. Otherwise the parameter shall have the qualifier const.

Also it is unclear why the function has return type char *. It looks like the declaration of the function is contradictive.

The second parameter of the function shall have at least the type size_t or that is better std::string::size_type. The type int can not accomodate all values of the type std::string::size_type.

The function could be declared without the second parameter.

A straightforward approach without using intermediate containers that requires dynamic memory allocation can look the following way

#include <iostream>
#include <string>

std::string & removeDuplicate( std::string &s )
{
    const char *p = s.c_str();

    std::string::size_type pos = 0;

    for ( std::string::size_type i = 0, n = s.size(); i < n; i++ )
    {
        std::string::size_type j = 0;
        while ( j < pos && s[i] != s[j] ) j++;

        if ( j == pos )
        {
            if ( i != pos ) s[pos] = s[i];
            ++pos;
        }
    }

    return s.erase( pos );
}

int main() 
{
    std::string s( "H e l l o" );

    std::cout << "\"" << s <<"\"\n";

    std::cout << "\"" << removeDuplicate( s ) <<"\"\n";

    return 0;
}

The program output is

"H e l l o"
"H elo"

Answer 5

This might be a bit advanced for newcomers to C++ but another solution makes use of the erase-remove idiom:

std::string removeDuplicates(const std::string& s) {
    std::string result = s;
    std::unordered_set<char> seen;

    result.erase(std::remove_if(result.begin(), result.end(), [&seen](char c)
        {
            if (seen.find(c) != seen.end())
                return true;

            seen.insert(c);
            return false;
        }),
    result.end());

    return result;
}

It basically uses a set to store characters that have been seen, shuffles the characters to be removed down to the tail (using std::remove_if) and erases the tail from the string.

Working version here.

Answer 6

This works too, a single line solution with an inbuild function.

cout<<str.erase(std::unique(str.begin(), str.end()), str.end());

Answer 7

Simple Answer

#include<bits/stdc++.h>
using namespace std;
string removeduplicate(string key){
    set<char>s;
    string ans="";
    for(int i=0;i<key.size();++i){
        if(s.find(key[i])==s.end()){
            s.insert(key[i]);
            ans.push_back(key[i]);
        }
    }
    return ans;

}



int main()
{
    string key="";
    cout<<"enter the key:";
    cin>>key;
    string ans1=removeduplicate(key);
    cout<<ans1;
    return 0;
}

Answer 8

So, after doing a bit of reading on the Internet I realized that I was trying to return a pointer to the local array in the removeDuplicates() function.

This is what works fine

#include <bits/stdc++.h>
using namespace std;
void removeDuplicates(string &s,int n){
    vector<char> vec;
    unordered_map<char,int> exists;
    int index = 0;
    for(int i=0;i<n;i++){
        if(exists[s[i]]==0)
        {
            vec.push_back(s[i]);
            exists[s[i]]++;
        }
    }
    for(auto x: vec)
        cout << x;
}

//driver code
int main(){
    string str;
    cin >> str;
    removeDuplicates(str,str.length());
    return 0;
}

PS: We can make the return type of function to vector as well.