5
\$\begingroup\$

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());
    }
}
\$\endgroup\$
4
\$\begingroup\$
  • 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.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ I'd like to add the class name which violates standard naming conventions. \$\endgroup\$ – Marvin Jan 15 '16 at 19:44
  • \$\begingroup\$ @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). \$\endgroup\$ – tim Jan 15 '16 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.