In-place remove all adjacent duplicates from the given string

Given a string, in-place remove all adjacent duplicates from it. The algorithm should continue removing adjacent duplicates from the string till no duplicate is present in the result.

 


For example,

Input string = ‘DBAABDAB’

The string left after removal of all adjacent duplicates is ‘AB’
‘DBAABDAB’ -> ‘D B AA B D A B’ -> ‘D BB D A B’ -> ‘DD A B’ -> ‘AB’
 

Input string = ‘ABADB’

The string left after removal of all adjacent duplicates is ‘ABADB’
‘ABADB’ -> ‘ABADB’
 

Input string = ‘ABDAADBDAABB’

The string left after removal of all adjacent duplicates is ‘AD’
‘ABDAADBDAABB’ -> ‘A B D AA D B D AA BB‘ -> ‘A B DD B D’ -> ‘A BB D’ -> ‘AD’


 

 
Naive approach is to recusively remove all adjacent duplicates in the string till no duplicates is left in the string. The problem with this approach is that it might require (n+1)/2 passes in the worst case resulting in O(n2) complexity. Here n is the string length.

 
C++ implementation –
 

Download   Run Code

Output:

The string left after removal of all adjacent duplicates is AB

 

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(1).

 

Can we do it in single pass?

Below solution does the trick in O(n) and O(1) space.

 
C++ implementation –
 

Download   Run Code

Output:

The string left after removal of all adjacent duplicates is AD

 
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
Unknown
Guest
Unknown

Incorrect answer for input:
ABDAADBDDAABBD