How to remove duplicate characters from String in Java? [Solved]

Hello all, how are you doing? It's been long since I have shared a coding problem from the interview. The last one I discussed was about finding Nth Fibonacci number, one of the popular dynamic programming problems. Nevermind,  today, you are going to learn about another popular coding problem.  How do you remove duplicate or repeated characters from String in Java is one of the frequently asked strings based coding problems from Interviews. This problem is very similar to removing duplicate elements from an array which we have discussed in the past here after all String is a character array in Java. If you know how to solve that problem, you should be able to solve this one as well.

There are three main ways to remove duplicates characters from String in Java;   First to sort the character array of string and then remove duplicate characters in linear time. 

Second, use an auxiliary data structure like Set to keep track of characters already seen and then recreate String from Set. This would tradeoff space for time, as space complexity of this solution would be O(n).

The third approach would be the brute force way of taking one string at a time and then removing all other occurrences of that string, rearranging the array and then starting with the next element. This would be a terrible solution because of multiple loops required.

Btw, in order to even think about these solutions, you need to have a good knowledge of various data structures and algorithms, those are fundamental parts of problem-solving in the programming world. And, if you feel you lack Data Structure and Algorithms skills you can revise them by joining Data Structures and Algorithms: Deep Dive Using Java course, one of the best to learn DS and Algorithms in Java.




How to delete repeated characters from a given String in Java

Now that, you are familiar with both problem and some approaches to remove duplicate characters from given String let's deep dive into the problem and analyze their time and space complexity.


Solution 1 - Sorting and Removing Duplicates

If you pay a little bit attention, then you can easily find that removing duplicate characters from String is nothing but removing duplicates from an array. Which means you can use all the ways we have used previously.

If we get character array from String and then sort it using MergeSort or QuickSort in O(Nlog N) time, we can easily remove duplicates in linear time, because they will be clubbed together. All you need to do is iterate over sorted character array, compare the current element with the previous element, and discard it if they are the same.

At the end of the iteration, your array only contains unique characters. Though this solution has a drawback, it doesn't preserve the original order of the element.

So if the interviewer asks you to keep elements in their original order, this solution will fall short, but for the practical purpose, this would work because you are dealing with duplicate characters.  If you want to learn more about stable sorting algorithms, I suggest you take a look at the Algorithms and Data Structures - Part 1 and 2 courses on Pluralsight.

How do you Remove Duplicate characters from String in Java? [Solved]

Btw, you would need a Pluralsight membership to get access to this course, which costs around $29 per month or $299 annually (14% discount).

If you don't have Pluralsight membership, I encourage you to get one because it allows you to access their 5000+ online courses on all the latest topics like front-end and back-end development, machine learning, etc. It also includes interactive quizzes, exercises, and the latest certification material.

They also provide a 10-day free trial without any commitment, which is a great way to not just access this course for free but also to check the quality of courses before joining Pluralsight.



Solution 2 - Using a Data Structure

The next solution is an exquisite one, and it demonstrates how you can simplify your algorithm by choosing an appropriate data structure. To remove duplicate characters from String, we need a data structure where insertion and search would be super fast.

If you take a hash table, we will get O(1) for insert and find operation. By the way, if you are using Java, then you have a better choice, HashSet, which is a combination of set and hash table data structure.

The Set data structure doesn't allow duplicate character, so if you convert your String to a character array, loop over it, add each element into HashSet, you will end up with a Set without duplicate characters. You can then convert that Set to String.

Our solution is based upon this knowledge, but it becomes more elegant by using StringBuffer for creating output String.add() method of Set return false if the element already exists in Set and by using that we can create a StringBuilder with only unique characters.

Converting a StringBuilder to String is a trivial task in Java but if you are not familiar with essential Java API then I suggest you join The Complete Java Masterclass by Tim Buchalaka on Udemy, one of the most comprehensive and up-to-date course to learn Java online.

Java Program to remove duplicate characters from String



Java Program to remove duplicate characters from String

Now that you have understood both solutions of removing duplicate characters from String let's write code to implement them. In this program, I have two methods for removing duplicates, one uses HashSet, an additional data structure while others remove duplicate characters in place without using any other data structure or additional memory.

I have made the program interactive so that you can play with it. When you run this program in your Eclipse IDE or from a command-line window, it will ask you to enter a string and then output the string without duplicate characters in the console.

This way you can test the solution and code with different inputs like null string, empty string, string without duplicate, string with duplicate, the string just containing duplicates, and with very short or long string inputs.


import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
/*
 * Java Program to remove duplicate characters from String.
 * We'll see two solutions for this problem, first one will 
 * show you how use of a suitable data structure like HashSet or HashMap
 * simplifies the solution and second one will remove the 
 * duplicate characters from String in place to boost performance. 
 */
 
public class Main {
 
  public static void main(String[] args) {
 
    System.out
        .println("Welcome to Java program to remove duplicate characters from String");
    Scanner scnr = new Scanner(System.in);
 
    System.out.println("Please enter a String with duplicate characters");
 
    String input = scnr.nextLine();
 
    String output = removeDups(input);
    System.out.println("String without duplicate characters is " + output);
 
    String withoutDups = removeDupsInPlace(input);
    System.out.println("String without duplicate characters in place is "
        + withoutDups);
    scnr.close();
 
  }
 
  /**
   * Java method to remove duplicate characters from String This method uses a
   * HashSet collection to get rid of duplicate characters.
   * 
   * @param word
   * @return String without duplicate characters
   */
  public static String removeDups(String word) {
    Set<Character> chars = new HashSet<>();
    StringBuilder output = new StringBuilder(word.length());
 
    for (int i = 0; i < word.length(); i++) {
      char ch = word.charAt(i);
      if (chars.add(ch)) {
        output.append(ch);
      }
    }
 
    return output.toString();
  }
 
  /**
   * A java method to remove duplicate characters from String in place. It
   * doesn't use additional buffer like HashSet we have used previously.
   * 
   * @param word
   * @return String without duplicates
   */
  public static String removeDupsInPlace(String word) {
    final StringBuilder output = new StringBuilder();
 
    for (int i = 0; i < word.length(); i++) {
      String character = word.substring(i, i + 1);
      if (output.indexOf(character) < 0) // if not contained
        output.append(character);
    }
    return output.toString();
  }
 
}
 
Output
Welcome to Java program to remove duplicate characters from String
Please enter a String with duplicate characters
Java
String without duplicate characters is Jav
String without duplicate characters in place is Jav


That's all about how to remove duplicate characters from String in Java. Apart from learning to solve this frequently asked coding problems, there are a couple of more things to learn. First, by using a data structure you can mostly simplify your logic and code. Second, by using additional memory you can bring down the time complexity of your algorithm or make your solution fast. You have also learned how to remove duplicates in place from String, which is very important from the interview point of view.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java by Heinz Kabutz


More String Problems to solve
If you are interested in solving more String based algorithm problems then here is the list of some of the frequently asked questions.
  • How to convert numeric String to an int? (solution)
  • How to Print duplicate characters from String? (solution)
  • How to program to print the first non-repeated character from String? (solution)
  • How to check if a string contains only digits?  (solution)
  • How to check if String is Palindrome? (solution)
  • How to count the number of vowels and consonants in a String? (solution)
  • How to check if two Strings are anagrams of each other? (solution)
  • How to find duplicate characters in a String? (solution)
  • How to reverse String in Java using Iteration and Recursion? (solution)
  • How to count the occurrence of a given character in String? (solution)
  • How to find all permutations of String? (solution)
  • 10 Algorithms Courses to Crack Programming Job Interviews (courses)
  • How to reverse words in a sentence without using a library method? (solution)
  • How to reverse a String in place in Java? (solution)
  • How to return the highest occurred character in a String? (solution)
  • 50+ Data Structure and Algorithms Interview Questions (questions)
Thanks for reading this coding interview question so far. If you like this String interview question then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.

No comments:

Post a Comment