Remove all Adjacent Duplicates from a String

In this lesson, we will learn how to remove all adjacent duplicates from a string using recursion.

We'll cover the following

What does “Removing Adjacent Duplicates from a String” Mean?

This means that whenever you find multiple instances of the same character side by side, remove all the extra instances (only one instance should remain).

Lower and upper case letters are considered different so the string Hhelo does not contain any duplicates.

Removing adjacent duplicates from a string
Removing adjacent duplicates from a string

Implementation

Press + to interact
def removeDuplicates(string):
    # Base Case1
    if not string:
        return ""
    # Base Case2
    elif len(string) == 1 :
        return string
    # Recursive Case1
    elif string[0] == string[1] :
        return removeDuplicates(string[1:])
    # Recursive Case2
    return string[0] + removeDuplicates(string[1:])
# Driver Code
print(removeDuplicates('Hellloo')) #returns Helo

Explanation

The approach we use here is to reduce the length of the string in each recursive call. However, if the current character is similar to the next character we discard it, i.e., we do not append it later on. However, if the current character is not similar to the next character we save it. We append it when the child function returns.

The code snippet above checks for 44 cases:

  1. If the input to the function is not a string.

    • In this case, we return an empty string: "".

  2. If the length of the string is 11.

    • There can be no duplicates in a string that contains only 11 character. Therefore, we return the string variable as it is in this case.

Conditions 11 and 22 will be our base case. There is no string manipulation occurring in both these cases.

  1. If the first and second elements of the string are same.

    • In this case, we discard the first occurrence and recursively call the same function with the first letter removed.

  2. If none of these 33 conditions are satisfied, we save the first element for later use and call the same function again with the first element removed. The saved element will be later appended to the beginning of the string when the recursive call returns.

Let’s have a look at the sequence of function calls:

In the next lesson, we will learn how to merge strings lexicographically.