Search⌘ K
AI Features
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. 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 so we return the string variable in this case.

Conditions 11 and 22 are the base case since there is no string manipulation occurring in either.

  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 take a look at the sequence of function calls:

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