Let's start by understanding the problem statement of Removing Duplicates From A String.
You are given a string, you have to eliminate the duplicates from the string.
Hint:
For removing the duplicates from the string you have to can use the unordered set in c++ where whenever any repeated character in a string is found you do not have to insert the character into the string, else you have to insert it into the set.
Quick Think:
For designing the algorithm for the above problem statement, you have to ponder over the following points:-
- Insert the character into the set if it is not inserted, else insert it into the set.
Algorithm:
Create an unordered set and follow the steps below to get a duplicate free string:-
Step1: Iterate through the string and check for the characters inserted into the set if the character is already in the set then, do not insert the character into the set else go to step 2.
Step2: Insert the character into the set if there is no same character in the set.
Step3: Now, iterate through the set and print the characters.
Implementation Of The Above Algorithm:
Now let's see the implementation of the above algorithm,
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str = "HELLO";
unordered_set<char> set_1;
for (int i = 0; i < str.length(); i++)
{
char d = str[i];
if (set_1.find(d) == set_1.end())
set_1.insert(d);
}
unordered_set<char>::iterator itr;
for (itr = set_1.begin(); itr != set_1.end(); ++itr)
cout << *itr;
return 0;
}
The time complexity of the above algorithm is O(n).
The output of the above algorithm: OHLE
.
Explanation Of The Above Algorithm:
Create an unordered set and follow the steps below to get the duplicate free string:-
- Let us take an example of the string as shown in the above diagram.
- Now, we iterate through the string and see that the first character of the string “HELLO” i.e., “H” is not in the set hence, we insert the character “H” into the set, and we move to the next character as shown in the above diagram.
- Now, “E” is also not present in the set hence, we insert “E” into the set, and we move into the next character in the string as shown in the above diagram.
- Similarly, “L” is also inserted into the set, and we move into the next character in the string as shown in the above diagram.
- Now, we get into the other “L” but this time this character already exists into the set, and so we will not push the character into the set, and we move into the next character in the string.
- Next, is the character “O” since this is not in the set so, we will insert the character into the set as shown in the above diagram.
- And, we obtain the output as shown in the above diagram.???????
NOTE: The output may not be in the correct order, as we have used here the unordered set.