Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Remove Duplicates from a String

Explore how to remove duplicate characters from a string using two main techniques: one with extra memory using a HashSet for linear time complexity, and another without extra memory but with quadratic time complexity. Understand the trade-offs in space and time complexity for these string manipulation methods.

We'll cover the following...

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

...