Recursively remove all adjacent duplicates

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 :
s = “adaaacad”

OUTPUT :
“adcad”

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
        //then add to output string
        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)
        removeAdjDup(s, k);// Shlemial Painter's Algorithm
 
    // If all characters were unique
    else return s;
}
 
int main()
{
    char str1[] = "abssbe";
    cout << removeAdjDup(str1, strlen(str1)) << endl;
 
    char str2[] = "adaaacad";
    cout << removeAdjDup(str2, strlen(str2)) << endl;
 
}

Try It

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
char* recRemoveAdjDup(char *s, char *last_removed)
{
    // 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++;
        return recRemoveAdjDup(s, last_removed);
    }
 
    //recursively remove adj duplicates in remaining string
    char* rem_str = recRemoveAdjDup(s+1, last_removed);
 
    //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 *removeAdjDup(char *s)
{
    char last_removed = '\0';
    return recRemoveAdjDup(s, &last_removed);
}

int main()
{
    char s1[] = "abssbe";
    cout << removeAdjDup(s1) << endl;
 
    char s2[] = "adaaacad";
    cout << removeAdjDup(s2) << endl;
 
    return 0;
}

Try It

 

Translate »