Remove adjacent duplicate characters from a string

Given a string, remove adjacent duplicates characters from it. In other words, remove all consecutive same characters except one.


 

For example,


Input: AABBBCDDD
Output: ABCD

 

The idea is to loop through the string and for each character, we compare it with its previous character. If the current character is different than the previous character, we make it as part of the resultant string, else we ignore it. The time complexity of this approach is O(n).

C

Download   Run Code

Output:

ABCD

C++

Download   Run Code

Output:

ABCD

Java

Download   Run Code


 

 
Here’s another variation of the problem where we’re asked to repeatedly remove all duplicates characters from a string until no adjacent duplicate is left. For example,


Input: ACABBACDDC
Output: AC

ACABBACDDC -> ACAACC -> AC

In the first iteration, ACABBACDDC is reduced to ACAACC. In the second iteration, ACAACC is further reduced to AC as it till contains duplicates. We stop then as all adjacent characters in the string AC are distinct.

 
The idea is to process the input string several times where in each pass, we scan the string from the beginning (Shlemial Painter’s Algorithm) and remove adjacent duplicates. We stop when the string remains unchanged in any pass.

 

Download   Run Code

Output:

AC

 
The time complexity of this approach would be O(n2).

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
kishore
Guest

Is O(N^2) the best for the problem 2?

XXXX
Guest

No