Recursively remove all adjacent duplicates

Code

#include <iostream>
#include <string.h>
using namespace std;

char* removeHelper(char *str, char *last_char){
     
    if (str[0] == '\0' || str[1] == '\0')
        return str;


    if (str[0] == str[1]){
        *last_char = str[0];
        while (str[1] && str[0] == str[1])
            str++;
        str++;
        return removeHelper(str, last_char);
    }
    char* newStr = removeHelper(str+1,last_char);
    if (newStr[0] && newStr[0] == str[0]){
        *last_char = str[0];
        return (newStr+1);
    }

    if (newStr[0] == '\0' && *last_char == str[0])
        return newStr;
    newStr--;
    newStr[0] = str[0];
    return newStr;
}
 
char *remove(char *str){
    char last_char = '\0';
    return removeHelper(str, &last_char);
}
 
int main(){
    char str[] = "acbbcddf";
    cout << remove(str) << endl;
    return 0;
}

Output

af

You can try by yourself with the help of online C++ Compiler.

Also read -  Decimal to Binary c++

Frequently Asked Questions

What are adjacent duplicates in a string?

Two adjacent characters in a string are adjacent duplicate characters if they are the same.

How do I recursively remove adjacent duplicates from a string?

Suppose we take a string s of length n. We will start from the leftmost character and remove duplicates at the leftmost corner, if any, ensuring the first character is different from its adjacent. Repeat the same for the remaining string of length n-1. Let the reduced string be s2. There are the following cases possible.

1. The first character of s2 matches s. Then, remove that character from s2.
2. The s2 string becomes empty since the last removed character is the same as the first character of s. Then the resultant output will be an empty string.
3. If the above-mentioned cases do not work, append the first character of s at the beginning of s2. 
   Then, return s2 as the output.

Key Takeaways

In this blog, we learned the concept of the C++ programming language using which we could code how to recursively remove all adjacent duplicate characters in a string. We hope that this blog has helped you enhance your knowledge, and if you wish to learn more, check out our  Coding Ninjas Blog site, Top 150 Interview puzzles and visit our Library. Do upvote our blog to help other ninjas grow.

Happy Learning!