Recursion: Remove adjacent duplicates in the string.

Problem Statement:

You are given a string, you need to remove adjacent duplicate.

Example:

Input: s = "abbaca"

Output: s = "ca"

Solution Explanation:

Solution is very simple.

Solution explanation has been provided with the code.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;


string solution(string str) 
{
    int len = str.size();

    if(len==1) 
    	return str; //if string has only one character, 

    for(auto i=0; i<len-1; i++)
    {
        if(str[i]==str[i+1])
        {
            str.erase(i,2); //remove the two duplicate character
            break; //break the loop after first pair
        }
    }
    if(len == str.size()) // if the size does not change, then there are no duplicate
    	return str;

    return solution(str);
}

int main() 
{
    string s = "abbaca";
    cout << solution(s) << endl; 
    return 0;
}

Output

ca