Given a string, 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,


The input string is 'DBAABDAB'
 
The string left after the removal of all adjacent duplicates is 'AB'
 
'DBAABDAB' —> 'D B AA B D A B' —> 'D BB D A B' —> 'DD A B' —> 'AB'
 
 
The input string is 'ABADB'
 
The string left after the removal of all adjacent duplicates is 'ABADB'
 
'ABADB' —> 'ABADB'
 
 
The input string is 'ABDAADBDAABB'
 
The string left after the 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'

The idea is to recursively remove all adjacent duplicates in the string until no duplicates are left. This idea is inspired by Schlemiel painter’s algorithm and implemented below in C, C++, Java, and Python:

C


Download  Run Code

Output:

The string left after the removal of all adjacent duplicates is AB

C++


Download  Run Code

Output:

The string left after the removal of all adjacent duplicates is AB

Java


Download  Run Code

Output:

The string left after the removal of all adjacent duplicates is AB

Python


Download  Run Code

Output:

The string left after the removal of all adjacent duplicates is AB

The time complexity of the above solution is O(n2) since it might require (n+1)/2 passes in the worst case, where n is the length of the input string. The auxiliary space required by the program is O(n) for recursion (call stack).