Search⌘ K
Home
Courses
Recursion for Coding Interviews in Python

Remove All Adjacent Duplicates from a String

Explore how to recursively remove all adjacent duplicates from a string, keeping only one instance of consecutive identical characters. Understand the base cases and recursive logic to manipulate strings effectively, preparing you for coding problems involving string processing.

We'll cover the following...

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

This means that we will remove all extra instances of a character when multiple instances are found together. In other words, only one instance should remain after this process.

Lower and upper case letters are considered different characters. Example: string Hhelo does not contain any duplicates.

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

Implementation

Python 3.5
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

To remove duplicates, we must reduce the length of the string with each recursive call. If the current character is similar to the following character, we discard it, meaning that we will not append it later on in the process. However, if the current character is not similar to the following character, we keep it. ...