Remove Duplicates from a string

Objective:  Given a string, write an algorithm to remove the duplicate characters in that string.

Example:

Input: tutorialhorizon
Output: tuorialhzn

Approaches:

There are multiple approaches to solve this problem-

  1. Use Sorting – (Will change the order of the characters)
  2. Use Hash Set – (Will change the order of the characters).
  3. Use Linked HashMap – (Will retain the order of the characters).
  4. Use Buffer Array – (Will retain the order of the characters).

Let’s discuss all the approaches

Sorting:

  1. Convert the string to character array. S
  2. Sort the array, this will bring all the identical characters together.
  3. Iterate through character array and remove the duplicate characters.
  4. This approach will change the order of characters.

Code:

import java.util.Arrays;
public class removeDuplicatesUsingSorting {
public static String removeDuplicates(String s) {
char[] chars = s.toCharArray();
Arrays.sort(chars); // O(nlogn)
String sbString = new String();
for (int i = 1; i < chars.length; i++) {
if(chars[i]!=chars[i1])
sbString +=chars[i];
}
//handle the first character
if(chars[0]!=chars[1])
sbString = chars[0] + sbString;
return sbString;
}
public static void main(String[] args) {
String s = "tutorialhorizon";
System.out.println(removeDuplicates(s));
}
}

Output: ahilnortuz

Hash Set:

  1. Convert the string to character array.
  2. Store all the characters in the Set.
  3. Set will store only one instance of each character
  4. Iterate through Set and print the characters.
  5. This approach will change the order of characters.

Code:

import java.util.HashSet;
import java.util.Iterator;
public class RemoveDuplicatesUsingSet {
public static String removeDuplicates(String s){
HashSet<Character> set = new HashSet<Character>();
char [] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
set.add(chars[i]);
}
Iterator<Character> iterator = set.iterator();
String sbString = new String();
while (iterator.hasNext())
sbString += iterator.next()+"";
return sbString;
}
public static void main(String[] args) {
String s = "tutorialhorizon";
System.out.println(removeDuplicates(s));
}
}

Output: artuhizlno

Linked Hash Set:

  1. Convert the string to character array.
  2. Store all the characters in the Linked Hash Set.
  3. Set will store only one instance of each character
  4. Iterate through Set and print the characters.
  5. This approach will retain the order of characters.

Code:

import java.util.Iterator;
import java.util.LinkedHashSet;
public class RemoveDuplicatesUsingLHM {
public static String removeDuplicates(String s) {
LinkedHashSet<Character> set = new LinkedHashSet<Character>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
set.add(chars[i]);
}
Iterator<Character> iterator = set.iterator();
String sbString = new String();
while (iterator.hasNext())
sbString += iterator.next() + "";
return sbString;
}
public static void main(String[] args) {
String s = "tutorialhorizon";
System.out.println(removeDuplicates(s));
}
}

Output: tuorialhzn

Buffer Array:

  1. Convert the string to character array.
  2. Create the boolean array of 256,( for all 0 – 255 ASCII characters)
  3. Iterate through character array from step one and set the Boolean array index ( index = ascii value of the character). Ignore if that index is already true.
  4. Create a separate array based on the index set as true in Boolean array.
  5. This approach will retain the order of characters.

Code:

public class RemoveDuplicates {
public static String removeDuplicates(String s){
char[] chrArr = s.toCharArray();
boolean[] asciiChrSet = new boolean[256];
StringBuilder stb = new StringBuilder();
for(int i=0;i<chrArr.length;i++){
if(asciiChrSet[chrArr[i]]){
continue;
}
asciiChrSet[chrArr[i]] = true;
stb.append(chrArr[i]);
}
return stb.toString();
}
public static void main(String[] args) {
String s = "tutorialhorizon";
System.out.println(removeDuplicates(s));
}
}

Output: tuorialhzn