...

/

Remove Duplicates from a String

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.

g a abbabcddbabcdeedebc b abcde a->b

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 characters
if (str == nullptr) {
return "";
}
// Create a hashet
unordered_set<char> set;
char* write_ptr = str;
char* read_ptr = str;
// Iterates loop till end of strinng
while (*read_ptr != '\0') {
// Add current character in hashset if its not in set before
if (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;
}

Time complexity

...