Remove all adjacent duplicates

Question

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

Answer 1

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);
}

Answer 2

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.

Answer 3

Ultimately you have to remove the duplicates from the String without using HashSet. One technique is to sort the char array first. The complete code is:

public class Test3 {
    public static void main(String[] args) {
        String str = "ABBCDAABBBBBBBBOR";
        char[] ca = str.toCharArray();

        Arrays.sort(ca);

        String a = new String(ca);
        System.out.println("original => " + a);
        int i = 0 ;
        StringBuffer sbr = new StringBuffer();
         while(i < a.length()) {
             if(sbr.length() == 0 ) {sbr.append(a.charAt(i));}
             if(a.charAt(i) == sbr.charAt(sbr.length() -1)) {i++ ;}
             else {sbr.append(a.charAt(i));}
         }//while

         System.out.println("After removing the duplicates => " + sbr);
    }//main
}// end1