Review on code for duplicate removal

Question

I am trying to remove duplicates from a string without using additional buffers.
This seems to work correct, I think. Can this be improved? Should I be doing it differently?

private static String removeDuplicates(char[] chars) {  

        if(chars == null) 
            return null;

        int len = chars.length;         
        for(int i = 0; i < len; i++){
            for(int j = i + 1; j < len;){
                if(chars[i] == chars[j]){
                    int temp = j;
                    while(temp < len - 1){
                        chars[temp] = chars[temp + 1];
                        temp++;
                    }
                    len--;
                }
                else
                    j++;
            }
        }

        return new String(chars, 0, len);
    }

Answer 1

A few stylistic comments :

1. I'd change the while loop for a for loop. It doesn't matter at all but I feel it better that way.

2. You could perform len--; before the while (or for) loop so that you can go til len instead of len - 1.

Then, as duplicates don't need to be close to each other (from what I understand), wouldn't it be easier to do something like (NOT TESTED AT ALL) :

private static String removeDuplicates(char[] chars) {  
    if(chars == null) 
        return null;
    int len = chars.length;
    int idx = 0;         
    for (int i = 0; i < len; i++) {
        char c = chars[i];
        bool dup = false;
        for (int j = 0; j < idx; j++) {
            if (c == chars[j]) {
                dup = true;
                break;
            }
        }
        if (!dup) {
            chars[idx] = c;
            idx++;
        }
    }

    return new String(chars, 0, idx);
}

The point would be to go through the string and for each characters, try to see if we have seen it already. If we haven't we store it, otherwise, we don't.

Answer 2

1. According to the Code Conventions for the Java Programming Language

   if statements always use braces {}.

   It's error-prone, so change

   if(chars == null) 
       return null;
   

   to

   if (chars == null) {
       return null;
   }
   

2. I agree with @codesparkle, it should throw an IllegalArgumentException or NullPointerException instead of returning with null.

   if (chars == null) {
       throw new NullPointerException();
   }
   

3. I'd use a for loop instead of inner while. It's more readable since it's an everyday for loop which iterates from j to len - 1. Furthermore, this loop should be extracted out to a well-named method:

   if (chars[i] == chars[j]) {
       len--;
       shiftArray(chars, len, j);
   } else {
       j++;
   }
   
   ...
   
   private static void shiftArray(final char[] array, final int arrayLength,
           final int startIndex) {
       for (int i = startIndex; i < arrayLength; i++) {
           array[i] = array[i + 1];
       }
   }
   

Answer 3

Are you sure you want to return null if the chars parameter is null?
Either it is acceptable to pass null into your method - you can then use the Special Case Pattern (also known as the NullObjectPattern) and return "";
Or, you decide that passing null is not acceptable. In that case, it is advisable to throw new IllegalArgumentException("chars may not be null!");

Why? Because if you return null, and some completely unrelated class uses the return value after passing in null as a parameter, that will likely generate a NullPointerException which is going to be much more of a headache to debug.

I'd personally be inclined to use the special case pattern because it treats the null argument as a legal case, reacting in the most non-disruptive way possible and keeping the system running, most likely without causing any random Exceptions later.

However, some may argue that it is important for failures to be caught early, and if you see a nullparameter as such a failure then definitely an IllegalArgumentExceptionwould make sense.

So even though it seems logical to pass back null when you receive it, it's better to do the thing that will protect you from long debugging session later, which is to either fail fast or to not fail at all by treating an null input as a valid case.

You said your intent was to

remove duplicates from a string without using additional buffers

yet you are passing in a char[]. You should pass in a String and then call ToCharArray even if the exercise book says you shouldn't. Otherwise, every time you call the method you will have first convert the input Stringto a char[], cluttering the call site every single time.

With an hard-to-understand algorithm like this, you should be using descriptive names. All these adjustments leave us with the following code:

private static String removeDuplicatesFrom(String original) {
    if (original == null) 
        return "";
    char[] chars = original.toCharArray();
    int length = chars.length;
    for (int current = 0; current < length; current++) {
        // compare the current char with all following chars
        // and delete it if one of them is the same
        for (int next = current + 1; next < length;) {
            if (chars[current] == chars[next]) { 
                // found a duplicate, need to delete it
                length--;
                for (int gap = next; gap < length; gap++) {
                    // delete the duplicate and left-shift all remaining chars
                    chars[gap] = chars[gap + 1];
                }
            } else
                next++;
                // current character is unique, move on
        }
    }
    return new String(chars, 0, length);
}

Notice that I was forced to write four comments because I failed to make the code more expressive. I hate comments, but I used them here because I think your requirements don't allow you to call other methods. Am I right? Otherwise, you should do it as in this StackOverflow answer.