Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

For this problem, I came up with this ugly solution of appending the characters to the output and in case there is adjacent duplicate deleting from the output. Considering StringBuilder.deleteCharAt(i) is O(N), performance is O(N) + O(N) = O(N).

Please critique this, if this is a right way.

public static String removeDuplicate(String s) {
StringBuilder builder = new StringBuilder();
char lastchar = '\0';
for (int i = 0; i < s.length(); i++) {
  String str = builder.toString();
  if (!str.equals("")
      && (str.charAt(str.length() - 1) == s.charAt(i))) {
    builder.deleteCharAt(str.length() - 1);
  } else if (s.charAt(i) != lastchar)
    builder.append(s.charAt(i));
  lastchar = s.charAt(i);
}
return builder.toString();
}

Sample input outputs:

Input: azxxzy
Output: ay

Input: caaabbbaacdddd
Output: Empty String

Input: acaaabbbacdddd
Output: acac

share|improve this question
6  
Why does it have to be recursive? ... and if it has to be recursive, why is your code not recursive? –  rolfl Mar 6 at 0:31
1  
Additionally, what does it mean to remove duplicates? If I give your code the word messy it returns mey... I was expecting mesy... which one is right? Why? –  rolfl Mar 6 at 0:34
    
@rolfl The examples added in Rev 2 clarify both issues. "messy""mey". "Recursively remove" refers to the problem statement, not the implementation. –  200_success Mar 6 at 5:58
add comment

2 Answers 2

up vote 3 down vote accepted

The problem is not that StringBuilder.deleteCharAt()is O(n) — you only ever use it to strip the last character. Rather, it's your builder.toString() that is problematic. It's an O(n) operation that is invoked in a loop up to n times.

Rather than using a StringBuilder, I recommend manipulating a char[] array directly. The problem, as you pointed out, is that StringBuilder.deleteCharAt(i) is O(n) because it shifts the rest of the string over. By doing your own accounting, you can just build the string correctly the first time.

public static String removeDuplicates(String s) {
    if (s.isEmpty()) {
        return s;
    }
    char[] buf = s.toCharArray();
    char lastchar = buf[0];

    // i: index of input char
    // o: index of output char
    int o = 1;
    for (int i = 1; i < buf.length; i++) {
        if (o > 0 && buf[i] == buf[o - 1]) {
            lastchar = buf[o - 1];
            while (o > 0 && buf[o - 1] == lastchar) {
                o--;
            }
        } else if (buf[i] == lastchar) {
            // Don't copy to output
        } else {
            buf[o++] = buf[i];
        }
    }
    return new String(buf, 0, o);
}
share|improve this answer
add comment

General

Your code formatting is all over the place. You should use consistent and structured indentation. See the Java Code-Style guide for, well, guidance.

if I take your code, and re-format it (Eclipse, CtrlA and CtrlshiftF), it looks like:

public static String removeDuplicate(String s) {
    StringBuilder builder = new StringBuilder();
    char lastchar = '\0';
    for (int i = 0; i < s.length(); i++) {
        String str = builder.toString();
        if (!str.equals("") && (str.charAt(str.length() - 1) == s.charAt(i))) {
            builder.deleteCharAt(str.length() - 1);
        } else if (s.charAt(i) != lastchar)
            builder.append(s.charAt(i));
        lastchar = s.charAt(i);
    }
    return builder.toString();
}

At least this allows us to see what you are doing.

Algorithm

A nice algorithm will take data from the input string, and add it to the output if it should be added. A system where you do multiple conversions, add things, and remove things, is complicated, and hard to follow.

Additionally, the null character \0 is actually a valid character in Java, so you may have (an extremely rare) bug.

I do not like that your code is removing all the duplicate values, it seems more practical to remove all but one of the duplicates, but you do not explain why it is supposed to be this way.

More Information required

The above, in itself, is a review, but, if you update your question with the requested details:

  • recursion yes/no/why?
  • dedup all, or all-but-one?

then I can add suggestions as to how to solve this in a more efficient way.

share|improve this answer
    
Actually I had issue while posting the code here, thats why formatting is all over the place. Anyways I follow Google style sheet in my eclipse, so it will be all right. –  Warrior Prince Mar 6 at 1:10
    
The question was : to remove adjacent duplicates from the code. I will post the valid inputs outputs in the question –  Warrior Prince Mar 6 at 1:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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