Remove duplicates from string without additional buffer

Question

I completed an exercise from the Cracking the Coding Interview:

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.

Follow-up: Write the test cases for this method.

I would like to ask whether my solution for the question is good enough, because the solution given in the book doesn't seem to work correctly.

import java.util.Arrays;
public class duplicateString{
 public static void rduplication(char [] word){
 if(word == null) return;
 int len = word.length;
 if(len<2) return;
 int count=0;
 for(int i =0;i<word.length;i++){
 for(int j=0;j<word.length;j++){
 if(word[i] == word[j]){
 count = count + 1;
 System.out.println(count);
 }
 if(word[i] == word[j] && count > 1){
 word[j] =0;
 }
 }
 count = 0;
 }
 System.out.println(Arrays.toString(word)); 
 }
 public static void main(String [] args){
 String word = "ababab";
 rduplication(word.toCharArray());
 }
}

Answer 1

• Method Signature: your method should return a result, instead of printing it to increase reusability and (automatic) testability.
• Complexity: The complexity of your method is higher than it has to be. One simple improvement would be to start the second loop at int j = i to avoid duplicate checks.
• Performance/Duplication: You check word[i] == word[j] twice. Just move the if (count > 1) check inside the first if to avoid this duplication.
• Argument Checks: Just returning in case of an invalid argument (null in this case) is not a good idea; throw an exception instead to avoid possible bugs in the future.
• Argument Checks: Returning nothing in case of a word length of 1 or 0 seems like a bug. I would expect an empty array or an array with the one entry to be returned (ie removeduplicate(['a']) should equal ['a'], not nothing).
• Result Value: Your array still contains entries in the positions where duplicate characters were (eg aaaaab -> [a, , , , , b]. This isn't what I would expect (also, the question talks about accepting a string, and presumably returning a string as well; it then also talks about arrays, so using an array internally - instead of eg charAt - is presumably correct, but I would still expect the input and output to be strings).
• count = count + 1 can be written as count++.
• Naming: removeDuplication would be a lot clearer. removeDuplicateCharacters would be even more precise.
• Formatting: Your spacing is inconsistent, leading to less readable code.
• Declare variables as late as possible to increase readability. For example, count isn't needed until inside the first loop.

Taking this all together, you would get something like this:

public static String removeDuplicateCharacters(String word) {
 Objects.requireNonNull(word);
 char[] wordArray = word.toCharArray();
 int len = wordArray.length;
 for (int i = 0; i < wordArray.length; i++) {
 int count = 0;
 for (int j = i; j < wordArray.length; j++) {
 if (wordArray[i] == wordArray[j]) {
 count++;
 if (count > 1) {
 wordArray[j] = 0;
 }
 }
 }
 }
 return String.valueOf(wordArray);
}

It's a bit too nested for my taste, but otherwise I think it's mostly ok.

• Marvin: I'd like to add the class name which violates standard naming conventions.
• tim: @Marvin oh, true, class names should always start with an upper-case character. DuplicateString also doesn't seem ideal, as it doesn't contain a duplicate string (but that's probably not relevant for this exercise).