Close

Couple elimination problem

Given a string of some symbols, write a program to transform a string by repeatedly eliminating two same symbols occurring together.
For example if the input string is ‘RGGB’ it will be reduced to ‘RB’ because ‘GG’ can be eliminated.

Here are some more examples of input – output
Input   | Output
——————-
GBRRBR  | GR
BGRGRR  | BGRG
GGBB    | <empty>
RGBGBR  | RGBGBR

Here is how we can solve this problem. Add each character into a temporary array. As you insert the character, check for previously inserted character. If it is same, erase that character otherwise add it to the temporary array. At the end, the temporary array has the transformed string.

C++ implementation of the above approach is given below.

 
#include <iostream>
#define MAX 100
using namespace std;

int main()
{
char string[MAX];
char temp[MAX];

cin>>string;
int i;
int tempInd = 0; //to track temp string

for( i = 0 ; string[i] != '' ; i++)
{
//If temp string has atleast one character
if( tempInd > 0)
{
//If previous, and current chars are same, erase
if( temp[tempInd-1] == string[i] )
{
tempInd--;
}
else//not same, append the char to temp
{
temp[tempInd++] = string[i];
}
}
else //temp is empty, simply append the character
{
temp[tempInd++] = string[i];
}
}
//append the NULL character at the end
temp[tempInd] = '';
//print the transformed string
cout<<temp<<endl;
return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *