Recursively Remove all Adjacent Duplicates

In this class, We discuss Recursively Remove all Adjacent Duplicates.

The reader can take the complete competitive coding course. Click Here.

Question:

Given a string S.

Recursively remove all adjacent duplicates in the string.

Example:

Input: abccdccab

Output: abdab

Example 2:

Input: abccbccba

Output: Null

Given input is abccbccba

after removing cc from the string, the remaining string is abbba

Now we can remove bbb from the string abbba

The remaining string is aa

Remove aa because of adjacent duplicates.

The final string is the null string.

Time complexity = O(|S|)

Space complexity = O(|S|)

The logic is explained in the video.

Code:

class Solution:

    def rremove (self, s):

        res = “”

        i = 0

        while i < len(s):

            if i + 1 < len(s) and s[i] == s[i+1]:

                i+=1

                while i < len(s) and s[i] == s[i-1]:

                    i+=1

            else:

                res += s[i]

                i+=1

        return res if len(res) == len(s) else self.rremove(res)

s=input()

ob=Solution()

res=ob.rremove(s)

print(res)