Problem Statement: Given a string “ABCCBCBA”, give an algorithm for recursively removing the adjacent characters if they are the same.
Example : ABCCBCBA ---> ABBCBA (after removing both the C at index 2,3) ABBCBA -------> ACBA (after removing both the B at index 1,2)
Approach :
First we need to check if we have a character pair; if yes, then remove it. Now check for next character and previous element. Keep canceling the characters until we reach the end of the array, or don’t find a pair. We can solve this problem recursively : remove a pair (if exist) then recursively call it for the rest of the string.
We can remove the pair by using string.erase() function.
Implementation :
#include <bits/stdc++.h>
using namespace std;
// Calling the removeDuplicate function
// and passing the string
string removeDuplicate(string s)
{
// it will check all the characters
for (int i=0 ; i<s.length() ; i++)
{
// checking if the character is same
// then removing the pair
if (s[i] == s[i+1])
{
s.erase(i,2);
// recursively caling removeDuplicate
// function for the rest string
s = removeDuplicate(s);
}
}
return s;
}
// Driver program
int main()
{
string s = "abccbcba";
cout<<"Original String : "<<s<<endl;
cout<<"Resultant string : "<<removeDuplicate(s)<<endl;
return 0;
}
Output : Original String : abccbcba Resultant string : acba
Time Complexity : O(n2)
Space Complexity : O(1)