Adjacent removal

Given a string. Write an algorithm to remove adjacent characters if they are same.

Ex. Input = abccbcba
remove cc => abbcba
remove bb => acba (final result)

Solution :

We just compare the last element with next and if equal remove both.
[In implementation we may also use stack]

Code :

// M = output size

void adjacent_removal(int input[], int N, int output[], int *M){

int i=1;
*M = 0

while(i < N){

while(input[i] == input[*M] && (i < N) && (*M >= 0)){

i++;
(*M)--;

}
output[++(*M)] = input[i];

}

}

Complexity :

• Time : O(N)
• Space : O(1)