# 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’

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

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂