Introduction

A common string problem is to remove repeated characters while keeping only the first occurrence of every character.

For example, if the string is programming, the character r, g, and m appear multiple times. We need to keep only their first occurrence.

This problem can be efficiently solved using a hashing technique.

Problem Statement

Given a string, remove all duplicate characters while preserving the order of their first occurrence.

Example

Input:programming

Output:
progamin

Constraints

  • 1 ≤ n ≤ 10⁵
  • The string can contain lowercase or uppercase characters.
  • The relative order of the first occurrences must be preserved.

Approach 1: Brute Force

Explanation

For every character, check whether it has already appeared in the result.

If it has not appeared, add it to the result.

Instead of using a hash set, we can search the result string for every character.

Steps

  1. Create an empty result string.
  2. Traverse the input string.
  3. For each character, search whether it already exists in the result.
  4. If it does not exist, add it.
  5. Return the result.

Dry Run

Input = "programming"

p → not present → add p
r → not present → add r
o → not present → add o
g → not present → add g
r → already present → skip
a → not present → add a
m → not present → add m
m → already present → skip
i → not present → add i
n → not present → add n
g → already present → skip

Result = "progamin"

Brute Force Code

Complexity Analysis

Time Complexity: O(n²) in the worst case.

Space Complexity: O(n) for the result.

Approach 2: Optimized Solution Using Hashing

Explanation

We can use a hash set to keep track of characters that have already appeared.

For every character:

  • If it is not present in the set, add it to the result and mark it as visited.
  • If it is already present, skip it.

This avoids repeatedly searching the result.

Steps

  1. Create an empty hash set.
  2. Create an empty result.
  3. Traverse the string.
  4. Check whether the current character exists in the set.
  5. If it does not exist, add it to the set and result.
  6. Otherwise, skip it.
  7. Return the result.

Dry Run

 Input = "programming"
Character    Set              Result
p            {p}              p
r            {p,r}            pr
o            {p,r,o}          pro
g            {p,r,o,g}        prog
r            already exists   prog
a            {p,r,o,g,a}      proga
m            {p,r,o,g,a,m}    progam
m            already exists   progam
i            {p,r,o,g,a,m,i}  progami
n            ...              progamin
g            already exists   progamin

Final Result = "progamin"

Optimized Code

Complexity Analysis

Time Complexity: O(n) on average.

Space Complexity: O(n).

Edge Cases

  • Empty string → ""
  • Single character → "a"
  • String with all unique characters → remains unchanged.
  • String with all identical characters → only one character remains.
  • Case-sensitive strings → A and a are treated as different characters.

Why This Problem is Important

This problem introduces the use of hashing with strings.

It helps build the foundation for:

  • Character frequency counting
  • Duplicate detection
  • Anagram problems
  • First unique character problems
  • String processing

Real-World Applications

Removing duplicates from strings is useful in:

  • Data cleaning
  • Text processing
  • Duplicate detection
  • Search optimization
  • Data normalization

Common Mistakes

  1. Removing characters without preserving their original order.
  2. Treating uppercase and lowercase characters as the same when the problem is case-sensitive.
  3. Using nested loops when hashing can provide better performance.
  4. Forgetting to add a character to the set after processing it.
  5. Confusing duplicate removal with sorting the characters.

Interview Tips

  • First explain the brute-force approach.
  • Then introduce a hash set to track already-seen characters.
  • Mention that the hash set provides O(1) average lookup.
  • Emphasize that the original order is preserved.
  • Be clear about whether the problem is case-sensitive.

Related Questions

  • Valid Anagram
  • First Unique Character
  • Frequency Count
  • Ransom Note
  • String Compression
  • Longest Substring Without Repeating Characters

Final Takeaway

To remove duplicate characters while preserving their first occurrence, traverse the string and maintain a hash set of characters already seen.

The hashing approach reduces the average time complexity from O(n²) to O(n).