How To 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 –
 
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 –
 


Output:

The string left after removal of all adjacent duplicates is AD.

Comments

Popular posts from this blog

How to change this to <%Html.ActionLink%> in my asp.net mvc application ?