# Recursively remove all adjacent duplicates

0
1062

## Given a string, write a function that will recursively remove all adjacent duplicates.

### Example 1

INPUT :
sÂ  = “abssbe”

OUTPUT :
“ae”

In the above example, after removing ‘s’ duplicates string becomes “abbe”, this string contains adjacent duplicates, so after removing ‘b’ duplicates the output string is “ae”

### Example 2

INPUT :

OUTPUT :

Time Complexity : O(n^2)

In this method the main idea is to first remove duplicates from the input string and if there are any duplicates in output string remove them recursively until we have no duplicates in output string.

## Algorithm

1. Add all the unique characters of input string to output string, if the length of input string is same as output string then stop, else

2. Take the output string as the input string to the function

## C++ Program

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

// This function recursively removes duplicates
// and returns modified string
char* removeAdjDup(char * s, int n)
{
int i;
int k = 0; // To store index of result

// Start from second character
for (i=1; i< n; i++)
{
// If the adjacent chars are different
if (s[i-1] != s[i])
s[k++] = s[i-1];

else
// Keep skipping (removing) characters
// while they are same.
while (s[i-1] == s[i])
i++;
}

// Add last character and terminator
s[k++] = s[i-1];
s[k] =  '\0';

// Recur for string if there were some removed
// character
if (k != n)

// If all characters were unique
else return s;
}

int main()
{
char str1[] = "abssbe";
cout << removeAdjDup(str1, strlen(str1)) << endl;

cout << removeAdjDup(str2, strlen(str2)) << endl;

}``````

Time Complexity : O(n)

## Algorithm

1. Start from the leftmost character and if there are any duplicates in left corner remove them

2. Now, the first character is different from its adjacent character, recur for the remaining string of length n-1

3. After the recursive call, all the duplicates are removed from the remaining string, call it as rem_strÂ  Now, we have first character and rem_str,

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.

## C++ Program

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

// Recursively removes adjacent duplicates from s and returns
// new string. last_removed is a pointer to last removed character
{
// If length of string is 1 or 0
if (s[0] == '\0' || s[1] == '\0')
return s;

// Remove leftmost same characters and recur for remaining
// string
if (s[0] == s[1])
{
*last_removed = s[0];
while (s[1] && s[0] == s[1])
s++;
s++;
}

//recursively remove adj duplicates in remaining string

//a) If first character of rem_str matches with the first character of original string,
//remove the first character from rem_str.
if (rem_str[0] && rem_str[0] == s[0])
{
*last_removed = s[0];
return (rem_str+1); // Remove first character
}

//b) If remaining string becomes empty and last removed character
// is same as first character of original string.
if (rem_str[0] == '\0' && *last_removed == s[0])
return rem_str;

//c) If the two first characters of s and rem_str don't match,
// append first character of s before the first character of
// rem_str.
rem_str--;
rem_str[0] = s[0];
return rem_str;
}

{
char last_removed = '\0';
}

int main()
{
char s1[] = "abssbe";