Duplicate chars

A string contains many characters. Some of them are duplicates. In some programs, these duplicate chars are not needed—we can remove them with a method.

To remove characters, we must first detect whether a character has been encountered before. We can search the string. But a lookup table can reduce searching.

Example method

Here we introduce removeDuplicateChars. This method receives a String. It creates two char arrays. These are used for recording encountered values and creating the result.

Detail This char array stores all the characters that have been encountered in the string. It needs to be able to fit all the chars.

Result In this array we place the result chars as we generate them. All duplicate chars are removed.

Detail For each char, we scan the table with a for-loop to see if the char has already been added. If not, we add it to both arrays.

public class Program {

    public static String removeDuplicateChars(String value) {
        int length = value.length();

        // This table stores characters that have been encountered.
        char[] table = new char[length];
        int tableLength = 0;

        // This array stores our result string.
        char[] result = new char[length];
        int resultLength = 0;

        for (int i = 0; i < value.length(); i++) {
            char current = value.charAt(i);

            // See if this character has already been encountered.
            // ... Test the table for a match.
            boolean exists = false;
            for (int y = 0; y < tableLength; y++) {
                if (current == table[y]) {
                    exists = true;
                    break;
                }
            }
            // If char has not been encountered, add it to our result array.
            if (!exists) {
                table[tableLength] = current;
                tableLength++;

                result[resultLength] = current;
                resultLength++;
            }
        }
        // Return the unique char string.
        return new String(result, 0, resultLength);
    }

    public static void main(String[] args) {

        // Test the removeDuplicateChars method.
        String test = "Java is cool";
        String result = removeDuplicateChars(test);
        System.out.println(result);

        test = "areopagitica";
        result = removeDuplicateChars(test);
        System.out.println(result);
    }
}Jav iscol
areopgitc

Algorithm notes

This algorithm is not perfect. But it will perform well on many strings. If a string is long, the number of duplicate chars that must be searched is reduced.

Tip This algorithm limits the search for duplicate chars to the number of unique chars, not the total number of chars in the string.

Tip 2 This improves the performance of the method on long strings. An even faster method could store chars by their ASCII values.

Method results

In the string "areopagitica" we find that the duplicate letters "a" and "i" are eliminated. In the "Java is cool" string, the second space is also eliminated.

With a lookup table, and a nested loop, we can remove duplicate chars from a string. We add chars to a char array and finally convert it to a string with the string constructor.