Lesson

8.6Remove Duplicates Characters

Problem Statement

Remove duplicate characters from a string.

Example Inputs

Input: "aabbcc"
- Output: "abc"
Input: "programming"
- Output: "progamin"
Input: "javascript"
- Output: "javscript"
Input: "hello world"
- Output: "helo wrd"

JavaScript Method - Using Only String Methods

Approach

To remove duplicate characters, we can use JavaScript string methods to create a unique string by iterating over each character and adding it only if it hasn't appeared before.

Steps

Initialize an empty string uniqueStr.
Loop through each character in the input string.
Check if the character does not exist in uniqueStr. If it doesn’t, add it.
Return uniqueStr as the result without duplicates.

Time & Space Complexity

Time Complexity: O(n^2), because for each character, we check if it exists in uniqueStr, which takes O(n) time.
Space Complexity: O(n), as a new string is created to store unique characters.

Code Snippet

Dry Run

Example input: "aabbcc"

Initialize: uniqueStr = ""
Loop through "aabbcc":
- a → Not in uniqueStr → uniqueStr = "a"
- a → Already in uniqueStr → uniqueStr = "a"
- b → Not in uniqueStr → uniqueStr = "ab"
- b → Already in uniqueStr → uniqueStr = "ab"
- c → Not in uniqueStr → uniqueStr = "abc"
Final output: "abc"

Alternative Approach - Using a Set Data Structure

Approach

Using a Set allows us to avoid duplicates automatically, as Sets only store unique values. We can loop through the string, add each character to the Set, and then convert the Set back to a string.

Steps

Initialize a new Set to store unique characters.
Loop through each character in the input string and add it to the Set.
Convert the Set back to a string using Array.from() and join().

Time & Space Complexity

Time Complexity: O(n), as each character is processed once.
Space Complexity: O(n), since we use a Set to store unique characters.

Code Snippet

Dry Run

Example input: "aabbcc"

Initialize: Set = {}
Loop through "aabbcc" and add to Set:
- Add a → Set = {a}
- Add b → Set = {a, b}
- Add c → Set = {a, b, c}
Convert Set to string: Array.from(Set).join('') → "abc"

Complexity Analysis

JavaScript Method (Using String Methods)

Time Complexity: O(n^2)
Space Complexity: O(n)

Alternative Approach (Using a Set)

Time Complexity: O(n)
Space Complexity: O(n)

Conclusion

Removing duplicate characters from a string can be done using string methods, but a Set provides a more efficient approach with linear time complexity. The Set-based approach is optimal for both simplicity and efficiency.

Previous Next