Remove Duplicates from a String
Remove duplicate characters from a string, which is passed by reference.
Statement
Given a string that contains duplicate occurrences of characters, remove the duplicate occurrences such that every character in the string appears only once.
Example
Sample input
abbabcddbabcdeedebc
Expected output
abcde
Try it yourself #
#include <iostream>#include <string>#include <unordered_set>using namespace std;void RemoveDuplicates(char* str){//TODO: Write - Your - Code}
Solution 1
- We keep two pointers or indices, one for the current reading position and one for the current writing position.
- Whenever we encounter the first occurrence of a character, we add it to the HashSet.
- Any character already existing in the HashSet is skipped on any subsequent occurrence.
Below is an overview of the algorithm:
read_pos = 0
write_pos = 0
for each character 'c' in str
if 'c' not found in HashSet
add 'c' to hashset
str[write_pos] = str[read_pos]
write_pos++
read_pos++
Let’s go through this step-by-step:
#include <iostream>#include <string>#include <unordered_set>using namespace std;string RemoveDuplicates(char* str) {// Returns the remaining string without iterated charactersif (str == nullptr) {return "";}// Create a hashetunordered_set<char> set;char* write_ptr = str;char* read_ptr = str;// Iterates loop till end of strinngwhile (*read_ptr != '\0') {// Add current character in hashset if its not in set beforeif (set.find(*read_ptr) == set.end()) {*write_ptr = *read_ptr;set.insert(*read_ptr);++write_ptr;}++read_ptr;}*write_ptr = '\0';return string(str);}int main() {string str1 = "dabbac";char* arr1 = const_cast<char*>(str1.c_str());cout << "1. Before: " << arr1 << endl;string out1 = RemoveDuplicates(arr1);cout << " After: " << out1 << endl;cout << "\n-----------------------------------------------------------------------------------------------------\n" << endl;string str2 = "aabbbccdddeee";char* arr2 = const_cast<char*>(str2.c_str());cout << "2. Before: " << arr2 << endl;string out2 = RemoveDuplicates(arr2);cout << " After: " << out2 << endl;cout << "\n-----------------------------------------------------------------------------------------------------\n" << endl;string str3 = "abcdef";char* arr3 = const_cast<char*>(str3.c_str());cout << "3. Before: " << arr3 << endl;string out3 = RemoveDuplicates(arr3);cout << " After: " << out3 << endl;cout << "\n-----------------------------------------------------------------------------------------------------\n" << endl;}