How to Remove Duplicate Characters from String in Java

This week's coding exercise is to remove duplicate characters from String in Java. For example, if given String is "aaaaaa" then output should be "a", because rest of  the "a" are duplicates. Similarly, if the input is "abcd" then 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 constraint 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 on comparative analysis.

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 e.g. Cracking the Coding Interview, which contains more than189 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 input String contains more than one duplicate characters.

This algorithm is also an example of 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 ASCII table

Our second solution is coded in removeDuplicatesFromString(String input) method. 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 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 character array and mark all characters which are seen by storing true in the corresponding index of 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 scheme 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 Java programming language. If you understand the logic you can write this solution in any programming language e.g. 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() &lt; 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 &lt; 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 t the Cracking the Coding Interview book. It contains more than 190 problems and their solutions from various tech companies programming job interviews.

Some more 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 Fibonacci series without recursion? (solution)
• How to find duplicate words in Java String? (solution)
• How do you print prime number up to a given number? (solution)
• How to check if a String is 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 Pyramid pattern of stars? (solution)