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.



C Code Complexity O(N^2) & Space O(1) Recursion

#include
#include
void couple_remove(char []);
int main(){
char arr[]="RGBBGBGR";// "RGBBGBGRRGRR";
couple_remove(arr);
printf("\n\n%s\n\n", arr);
return 0;
}

void couple_remove(char arr[]){
int remove=0,i,j;
int len=strlen(arr);
for(i=0;i if( arr[i]== arr[i+1] ){
for(j=i+2;j<=len;j++) {
arr[i]=arr[j];
i++;
remove=1;
}
}
if ( remove )
break;
}
if ( remove )
couple_remove(arr);
}

Rune Here https://ideone.com/urZEo


Java Code Complexity O(n) & Space O(n) Iterative

import java.util.Stack;
class CoupleElimination {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Stack st = new Stack();
String inputString = "RGBBGBGR";
for( int i=0 ; i < inputString.length() ; i++ )
{
char ch = inputString.charAt(i);
char top ;
if( !st.empty())
{
top = st.peek();

if( top == ch)
st.pop();
else
st.push(ch);
}

else
st.push(ch);
}
String result = "";
while( !st.empty() )
{
result = st.pop()+result;
}
System.out.println(result);
}
}

Run Here https://ideone.com/UF0Ao