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.
...