Java program to remove adjacent duplicate characters from a string

Removing adjacent duplicate characters from a string is a unique problem to solve. Lets see how this can be solved.

UseCases

  • Input = “geeksforgeek” , Output = “gksforgk”
  • Input = “acaaabbbacdddd” , Output = “acac”

Method to solve

This can be solved by using for loop or by using recursion, but I am using recursion here to solve this.

Code snippet

String removeDuplicates(String text){
        int count = 1;
        int charCount=1;
        int index=0;
        while(count<text.length()){
           char newAdjacentCharacter = text.charAt(count-1);
           char newCharacter = text.charAt(count);
            if(newCharacter==newAdjacentCharacter){
                if(index==0){
                    index = count-1;
                }
               charCount++;
            }else if(charCount>1){
                break;
            }
            count++;
        }
       
       if(charCount>1){
        String duplicateText = text.substring(index,index+charCount);
        text = text.replace(duplicateText,"");        
        return removeDuplicates(text);
       }else {
           return text;
       }
    }

Dry Passes

By using the above solution, here are outputs you will get after every pass

Pass 1 => acaaabbbacdddd
Pass 2 => acbbbacdddd
Pass 3 => acacdddd
Pass 4 => acac

Runtime Complexity

Now runtime complexity of the above solution is O(L*S), where L stands for number of while loop iteration and S stands for the number of recursive calls made.