Friday, May 17, 2013

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] != '\0' ; 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] = '\0';
 //print the transformed string
 cout<<temp<<endl;
 return 0;
}