Question:
You have a string "RGBBGBGR". Eliminate the pairs (two same chars adjacent to each other) recursively.

Example:
RGBBGBGR --> RGGBGR-->RBGR
Answer: Here recursively mean not a recursive function but to do it in the manner shown in example. Still we can do it recursively like below:

Fun_rcur(string)
{
if pairs
 Remove pairs in string
 Fun_recur(string)
Else
 Return
}
But this is very costly:
1) Extra space (stack space for recursive calls)
2) You need to go through entire string in each recursive call.

Lets see an iterative approach for the same. We should check if we have character pair then cancel it and then check for next character and previous element. Keep canceling the characters until you either reach start of the array, end of the array or not find a pair.


Code:

void remove_pair(char* input)
{
    int len = strlen(input);
    int i, j = 0;
    
    for (i=1; i <= len; i++)
    {
        //Cancel pairs
        while ((input[i] == input[j]) && (j >= 0))
        {
            i++;
            j--;
        }
        input[++j] = input[i];
    }
    return;
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.