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 string left after the removal of all adjacent duplicates is 'ABADB'

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

Output:

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

## C++

Output:

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

## Java

Output:

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

## Python

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).