How to Remove Duplicate Characters from String in Java? Example (original) (raw)

This week's coding exercise is to remove duplicate characters from String in Java. For example, if the given String is "aaaaaa" then the output should be "a", because the rest of the "a" are duplicates. Similarly, if the input is "abcd" then the output should also be "abcd" because there is no duplicate character in this String. By the way, you can not use any third-party library or Java API method to solve this problem, you need to develop your own logic or algorithm and then write code to implement that algorithm. This is one of the interesting problems from Java coding interviews and you can use this program to weed out Java programmers who cannot write code.

This problem is much better than Fizzbuzz because it requires more logic and coding than solving Fizzbuzz.

In this article, I'll share two ways to remove duplicate characters from String and will discuss the pros and cons, the time complexity of each solution.

Sometimes, a choice is restricted by putting additional constraints put by the interviewer, that's why it's better to know multiple ways to solve a problem. This not only helps in understanding the problem better but also in comparative analysis.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join comprehensive Data Structure and Algorithms courses like these Data structures and Algorithms courses to fill the gaps in your understanding.

Btw, This is a very popular coding-based question on tech companies' job interviews and you will this problem in all good coding interview questions books like Cracking the Coding Interview, which contains more than 189 code-based problems from various interviews.

Solution 1 - Replacing duplicate with NUL character

Our first solution is coded in the method removeDuplicates(String word), it takes a String and returns another String without duplicates. This algorithm goes through each character of String to check if it's a duplicate of an already found character.

It skips the duplicate character by inserting 0, which is later used to filter those characters and update the non-duplicate characters.

The Time Complexity of this solution is O(n^2), excluded to uniqueString() method, which creates a String from the character array. This method will work even if the input string contains more than one duplicate character.

This algorithm is also an example of a brute force algorithm to solve a programming problem. To learn more about different types of algorithms in the programming world e.g. greedy algorithm, you should check Introduction to Algorithm by Thomas Cormen, one of the best books to learn computer algorithms.

Solution 2 - Using an ASCII table

Our second solution is coded in removeDuplicatesFromString(String input) method. This solution assumes that the given input String only contains ASCII characters. You should ask this question to your Interviewer, if he says ASCII then this solution is Ok.

This Algorithm uses an additional memory of constant size. It creates a boolean array of length 256 to accommodate all ASCII characters. Initially, all array elements are false. This array is used as a Set to check if an ASCII character is seen already or not. You iterate over the character array and mark all characters which are seen by storing true in the corresponding index of the ASCII array.

For example, if input String is "abcda" then ASCII['a'] = true means at index 65 true is stored, next time when you find this character 'a', you know that this character has appeared before because of true element hence it's duplicate, so you store here ZERO or NUL.

Later you remove all those characters and create a unique String as output. See Unicode demystified to learn more about encoding schemes in the computer world.

Java Solution - Remove duplicate characters from given String

Here is my solution for the problem of removing repeated or duplicate characters from given String in the Java programming language. If you understand the logic you can write this solution in any programming language like C, C++, C#, Python, or JavaScript.

/**

Java Program to remove duplicate characters from String.
@author Javin Paul */ public class RemoveDuplicateCharacters{

public static void main(String args[]) {
```
 System.out.println("Call removeDuplicates(String word) method ....");
 String[] testdata = {"aabscs", "abcd", "aaaa", null, "",
                         "aaabbb", "abababa"};

 for (String input : testdata) {
     System.out.printf("Input : %s  Output: %s %n",
                    input, removeDuplicates(input));
 }

 System.out.println("Calling removeDuplicatesFromString(String str).");
 for (String input : testdata) {
     System.out.printf("Input : %s  Output: %s %n",
           input, removeDuplicatesFromString(input));
 }
```
}

/*
- This algorithm goes through each character of String to check if its
- a duplicate of already found character. It skip the duplicate
- character by inserting 0, which is later used to filter those
- characters and update the non-duplicate character.
- Time Complexity of this solution is O(n^2), excluded to
- UniqueString() method, which creates String from character array.
- This method will work even if String contains more than one duplicate
- character. */ public static String removeDuplicates(String word) { if (word == null || word.length() < 2) { return word; }
  
  int pos = 1; // possible position of duplicate character char[] characters = word.toCharArray();
  
  for (int i = 1; i < word.length(); i++) { int j; for (j = 0; j < pos; ++j) { if (characters[i] == characters[j]) { break; } } if (j == pos) { characters[pos] = characters[i]; ++pos; } else { characters[pos] = 0; ++pos; } }
  
  return toUniqueString(characters);
}

/*
- This solution assumes that given input String only contains
- ASCII characters. You should ask this question to your Interviewer,
- if he says ASCII then this solution is Ok. This Algorithm
- uses additional memory of constant size. */ public static String removeDuplicatesFromString(String input) { if (input == null || input.length() < 2) { return input; }
  
  boolean[] ASCII = new boolean[256]; char[] characters = input.toCharArray(); ASCII[input.charAt(0)] = true;
  
  int dupIndex = 1; for (int i = 1; i < input.length(); i++) { if (!ASCII[input.charAt(i)]) { characters[dupIndex] = characters[i]; ++dupIndex; ASCII[characters[i]] = true; } else { characters[dupIndex] = 0; ++dupIndex; } }
  
  return toUniqueString(characters);
}

/*
- Utility method to convert Character array to String, omitting
- NUL character, ASCII value 0. */ public static String toUniqueString(char[] letters) { StringBuilder sb = new StringBuilder(letters.length); for (char c : letters) { if (c != 0) { sb.append(c); } } return sb.toString(); }

}

Output Call removeDuplicates(String word) method .... Input : aabscs Output: absc Input : abcd Output: abcd Input : aaaa Output: a Input : null Output: null Input : Output: Input : aaabbb Output: ab Input : abababa Output: ab

Calling removeDuplicatesFromString(String str) method .... Input : aabscs Output: absc Input : abcd Output: abcd Input : aaaa Output: a Input : null Output: null Input : Output: Input : aaabbb Output: ab Input : abababa Output: ab

That's all about how to remove duplicate characters from given String in Java. You can use this logic to remove duplicate values from the array in Java as well. If you need more practice, you can check out these coding interview courses. It contains more than 190 problems and their solutions from various tech companies programming job interviews.

Other coding problems for practicing in Java:

How to reverse a String in place in Java? (solution)
Top 20 Amazon and Google Interview Questions? (list)
How to reverse an ArrayList in place in Java? (solution)
How to print the Fibonacci series without recursion? (solution)
How to find duplicate words in Java String? (solution)
How do you print prime numbers up to a given number? (solution)
How to check if a String is a Palindrome in Java? (solution)
How to find duplicate elements in an array? (solution)
Write a program to print Floyd's triangle in Java? (solution)
How to find the largest prime factor of a number in Java? (solution)
How to count the number of words in a given String? (solution)
Write a Java program to print Pascal's triangle? (solution)
How to find all permutations of a String in Java? (solution)
Write a Java program to print the pyramid pattern of stars? (solution)

Thank you for reading this article so far. If you find this coding problem interesting and solution please share it with your friends. If you have any questions, please ask.

And lastly one question for you? How do you find if String contains only unique characters and no duplicates? This one is also a popular interview question and If you know let me know your approach and code in comments, all the best !!.