Recursively remove all adjacent duplicates | GeeksforGeeks

Recursively remove all adjacent duplicates | GeeksforGeeks
Given a string, recursively remove adjacent duplicate characters from string. The output string should not have any adjacent duplicates.

Using Stack
    for(i=0;i<n;i++)
    {
        if(vec.empty()) {vec.push_back(s[i]); continue;}
        if(s[i]==vec.back())
        {
            if(!vec.empty()) vec.pop_back();
            for(j=i+1;((s[j]==s[i])&&(j<n));j++) ;
            i=j-1;
        }
        else vec.push_back(s[i]);
    }
    for(i=0;i<vec.size();i++) printf("%c",vec[i]);

We can remove all duplicates in O(n) time.
1) Start from the leftmost character and remove duplicates at left corner if there are any.
2) The first character must be different from its adjacent now. Recur for string of length n-1 (string without first character).
3) Let the string obtained after reducing right substring of length n-1 be rem_str. There are three possible cases
……..a) If first character of rem_str matches with the first character of original string, remove the first character from rem_str.
……..b) Else if the last removed character in recursive calls is same as the first character of the original string. Ignore the first character of original string and return rem_str.
……..c) Else, append the first character of the original string at the beginning of rem_str.
4) Return rem_str.

      static String removeUtil(String str, char last_removed)

      {

             // If length of string is 1 or 0 

             if (str.length() == 0 || str.length() == 1)

                 return str;

  

             // Remove leftmost same characters and recur for remaining  

             // string 

             if (str.charAt(0) == str.charAt(1))

             {

                 last_removed = str.charAt(0);

                 while (str.length() > 1 && str.charAt(0) == str.charAt(1))

                       str = str.substring(1, str.length());

                 str = str.substring(1, str.length());

                 return removeUtil(str, last_removed); 

             }

  

             // At this point, the first character is definiotely different  

             // from its adjacent. Ignore first character and recursively  

             // remove characters from remaining string 

             String rem_str = removeUtil(str.substring(1,str.length()), last_removed);

  

             // Check if the first character of the rem_string matches with  

             // the first character of the original string

             if (rem_str.length() != 0 && rem_str.charAt(0) == str.charAt(0))

             {

                last_removed = str.charAt(0);

                return rem_str.substring(1,rem_str.length()); // Remove first character

             } 

  

  

             // If remaining string becomes empty and last removed character 

             // is same as first character of original string. This is needed 

             // for a string like "acbbcddc" 

             if (rem_str.length() == 0 && last_removed == str.charAt(0))

                 return rem_str;

  

             // If the two first characters of str and rem_str don't match,  

             // append first character of str before the first character of 

             // rem_str

             return (str.charAt(0) + rem_str);

      }

http://algorithmsforever.blogspot.com/2011/11/adjacent-removal.html

Solution :

We just compare the last element with next and if equal remove both.
[In implementation we may also use stack]

Code :

// M = output size

void adjacent_removal(int input[], int N, int output[], int *M){

int i=1;
*M = 0

while(i < N){ 

while(input[i] == input[*M] && (i < N) && (*M >= 0)){

i++;
(*M)--;

}
output[++(*M)] = input[i];

}

}

http://learncsbyexample.blogspot.com/2016/01/remove-adjacent-duplicates.html