remove duplicate characters

2 Ways to Remove Duplicate Characters from a String in O(n) Time

Given an input string, the goal is to remove duplicate characters from a string and the output string should have the resultant string without modifying the order of characters in the original string.

Let’s solve the above problem in O(n) time using Method 1: Constant space i.e., O(1) space and using Method 2: Hashing

Method 1: Algorithm – Constant Space

Our approach here is to use bits of a count variable to mark the presence of a character in the input string. Below is the algorithm to remove duplicate characters from a string in O(1) extra space

Solution 1: Remove duplicate characters (Constant Space)

Output

Time Complexity – O(n)

Space Complexity – O(1)

Method 2: Algorithm – Hashing

Below is the algorithm to remove duplicate characters from a string using LinkedHashSet.

Solution 2: Remove duplicate characters (Hashing)

Output

Time Complexity – O(n)

Recommended Posts

Reference

Leave a Reply

avatar
  Subscribe  
Notify of