Posts

Showing posts from December, 2018

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 AABB‘ -> ‘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 –