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

1) Declare and initialize count variable to keep track of visited characters in the input string. 
   It is 32 bit integer represented as (00000000000000000000000000000000)
2) Declare variable 'x' to store ASCII value of a character.
3) Declare and initialize variable 'outStrLength' to keep track of length of final output string.
4) Traverse through each character in the input string
   4.1) Get current character's ASCII value x (x = ASCII value of character - 97). 
        This is to ensure value of 'a' as 0, value of 'b' as 1 and so on
   4.2) Check if x'th bit of counter is 0,
        if yes then it means current character is encountered for the first time.
        4.2.1) Save the current character at the index "outStrLength" of string.
        4.2.2) Mark the presence of current character as visited.
        4.2.3) Increment the length
5) Print the substring of size "outStrLength" from index 0

Solution 1: Remove duplicate characters (Constant Space)

package com.sneppets.dsalgo.examples;

import java.util.Arrays;

/**
 * Remove duplicate characters from a string in O(n) time and O(1) constant space 
 * @author sneppets.com
 */
public class RemoveDuplicateStringConstantSpace {

	public static void main (String[] args)
	{
		String inStr = "sneppets";
		removeDuplicates(inStr);
	}

	private static void removeDuplicates(String inStr) {
		
		//Declare and initialize count variable, 
		//to keep track of visited characters in the input string.
		//It is 32 bit integer represented as (00000000000000000000000000000000)
		int count = 0;
		char[] outStr = inStr.toCharArray();
		int i=0;
		
		//Declare variable to store ASCII value of a character
		int x;
		
		//Declare and initialize variable to keep track of length of final string 
		int outStrLength = 0;
		
		//Traverse through each character in the input string
		while (i < outStr.length)
		{
			//The ASCII value of 'a' is 97
			//Get current character's ASCII value (x)
			//x = ASCII value of character - 97. This is to ensure value of 'a' as 0, value of 'b' as 1 and so on
			x = outStr[i] - 97;
			
			//check if x'th bit of counter is 0,
			//if yes then current character is encountered for the first time
			if((count & (1<<x)) == 0)
			{
				//save the current character at the index "outStrLength" of string.
				outStr[outStrLength] = (char)('a' + x);
				
				//Mark the presence of current character as visited
				count = count | (1 << x);
				//increment the length
				outStrLength++;
				
			}
			i++;
		}		
		//print the substring of size "outStrLength" from index 0
		System.out.println(Arrays.copyOfRange(outStr, 0, outStrLength));		
	}
}

Output

snept

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.

1) Create new LinkedHashSet, so that you could remove duplicates while maintaining order of characters.
2) Traverse through the characters in the input string
   2.1) Add the current character to newly created set if it is not already present.
3) Print the string after removing duplicate characters with order of characters maintained.

Solution 2: Remove duplicate characters (Hashing)

package com.sneppets.dsalgo.examples;

import java.util.LinkedHashSet;

/**
 * Remove duplicate characters from a string, 
 * while maintaining order of characters in O(n) time using Hashing 
 * @author sneppets.com
 */
public class RemoveDuplicateStringHashing {
	
	public static void main (String[] args)
	{
		String inStr = "sneppets";
		removeDuplicates(inStr);
	}

	private static void removeDuplicates(String str) {
		
		//create new LinkedHashSet, so that you could remove duplicates 
		//while maintaining order of characters
		LinkedHashSet<Character> lhs = new LinkedHashSet<>();
		
		//Traverse through the characters in the string
		for(int i =0; i<str.length(); i++)
		{
			//Add the current character to this set if it is not already present
			lhs.add(str.charAt(i));
		}
		//print string after removing duplicate characters
		printStringInLHS(lhs);		
	}

	private static void printStringInLHS(LinkedHashSet<Character> lhs) {
		//Traverse through LinkedHashSet and print string after removing duplicate characters
		for (Character ch: lhs)
		{
			System.out.print(ch);
		}
		
	}

}