0

Given a string of characters, we need to remove all the duplicate characters in the given string.

This is tutorial file given by my professor.

This is working properly except for the test cases like:

Test case:

Expected output:

{a,b,a,c,d} --> {a,b,c,d}

Output Received:

{a,b,a,c,d} --> {a,b,a,c,d}

My code:

#include <bits/stdc++.h>

using namespace std;



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

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

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

   return (ch+ans);
}   

int main(){

   cout<<removeDup("abacd")<<endl;

   return 0;
}

Please send the solution using recursion,if possible.

pekking
  • 23
  • 2
  • 2
    There are many ways to solve this. One is to sort the list, then duplicate elements are going to be consecutive, so finding them will be easy. – Aykhan Hagverdili Jun 14 '21 at 17:57
  • Obligatory links to [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) Using both together can get really bad. Sounds like you're not facing a bug yet, but when you have a mystery error in your code, removing these two lines should be among the first things you try. Preferably avoid all of the problems caused by them by not using them in the first place – user4581301 Jun 14 '21 at 18:02
  • https://www.geeksforgeeks.org/remove-duplicates-from-a-given-string/ – dixit_chandra Jun 14 '21 at 18:11
  • I recommend Ignoring the above link. It's the kind of example that makes you a worse C++ programmer rather than better. – user4581301 Jun 14 '21 at 20:25

2 Answers2

0

The typical way to remove duplicate elements in non-sorted array is managing a set of elements already seen and add the element to the result only if it is not seen before.

#include <iostream>
#include <string>
#include <set>
using std::cout;
using std::endl;
using std::string;

void removeDupInternal(const string& data, size_t pos, string& out, std::set<char>& used){
    if (pos < data.size()){
         if (used.find(data[pos]) == used.end()){
             out += data[pos];
             used.insert(data[pos]);
         }
         removeDupInternal(data, pos + 1, out, used);
    }
}

string removeDup(string s){
    string result;
    std::set<char> used;
    removeDupInternal(s, 0, result, used);
    return result;
}

int main(){

   cout<<removeDup("abacd")<<endl;

   return 0;
}
MikeCAT
  • 73,922
  • 11
  • 45
  • 70
0

can be simply done by:

    string input="abagkfcd";

    string output= "";
    for(char& ch: input)
        if(output.find(ch) == string::npos)
            output +=  ch;

    cout<<output;

Using Recursion; may not be my best but here is the try

string removeDup(string ip, string& op){

    if(not ip.empty())
    {
        if(op.find(ip[0]) == string::npos)
            op += ip[0];
        removeDup(std::string(ip.begin()+1, ip.end()), op);
    }
    return op;

}

int main(){

    string input="abagkggffkfcd";
    string output{};

    removeDup(input, output);

    cout<<output;

    return 0;
}
dixit_chandra
  • 468
  • 3
  • 14