Removing duplicate characters from the given string

Problem

Remove the duplicate characters from the given string.

Solution

  • Use Java Set. LinkedHashSet used as it preserves insertion order. Complexity for adding items in LinkedhashSet is O(1).
  • This solution prints the duplicates while traversing through the array.
  • Time complexity – O(n) Linear.
  • Implementation in Java.
package com.computepatterns.problemsolving.string;

import java.util.LinkedHashSet;
import java.util.Set;

/**
 * Remove duplicates from the given String.
 * Leverage JDK set. Set doesn't allow duplicates.
 */
public class RemoveDuplicates {

    String removeDuplicates(String input){
        // LinkedHashSet over HashSet as LinkedHashSet preserve order.
        // Set doesn't allow duplicates.
        Set<Character> characterSet = new LinkedHashSet<Character>();

        for (int i = 0; i < input.length(); i++) {
            if(!characterSet.add(input.charAt(i))){
                System.out.printf("Duplicate character - %c\n", input.charAt(i));
            };
        }
        return characterSet.toString();
    }

    public static void main(String[] args) {

        String output = new RemoveDuplicates().removeDuplicates("Hello World!!!");
        System.out.printf("String after removing duplicates - %s", output);
    }
}

Link to github code