Remove adjacent duplicate characters in a String(java) i.e input:aaaabbbccdbbaae output: abcdbae

Question

my code does not give expected output,but dry run works fine.please give a look where is the problem

public static StringBuffer singleOccurence(String s)
{
 StringBuffer sb = new StringBuffer(s);
 int length=s.length();


 for(int i=0; i< length ; i++)
 {
  for(int j=i; i<length&&j<length ; j++)
  {
    if(sb.charAt(i)!=sb.charAt(j+1)) 
         i=j+1;
    else
    sb.deleteCharAt(j+1);
   } 
 }

 return sb;
}

also gives StringIndexOutOfBounds

Answer 1

Your method is doing a lot of unnecessary work.

The problem can be solved by iterating over the string once and comparing each character to the one that precedes it:

public static StringBuilder singleOccurence(String s)
{
    StringBuilder sb = new StringBuilder();
    if (s.length() > 0) {
        char prev = s.charAt(0);
        sb.append(prev);
        for (int i = 1; i < s.length(); ++i) {
            char cur = s.charAt(i);
            if (cur != prev) {
                sb.append(cur);
                prev = cur;
            }
        }
    }
    return sb;
}

This method has linear time complexity.

Answer 2

I would use a regex:

String input = "aaaabbbccdbbaae";
String regex = "(.)(\\1)+"; // matches any character followed by the same one(s)
String output = input.replaceAll(regex, "$1");
System.out.println(output); // abcdbae

Your method would be:

public static String singleOccurence(String s) {
    return s.replaceAll("(.)(\\1)+", "$1");
}

Answer 3

Easiest way is to traverse string from end to start:

public static StringBuffer singleOccurence(String s)
{
    StringBuffer sb = new StringBuffer(s);        
    for (int i = sb.length() - 2; i >= 0; i--)
        if (sb.charAt(i) == sb.charAt(i + 1))
             sb.deleteCharAt(i + 1);
    return sb;
}