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: ayInput: caaabbbaacdddd   Output: Empty StringInput: acaaabbbacdddd   Output: acac
Remove all adjacent duplicates
java;algorithm;performance
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);}