Write Python Program to Recursively Remove All Adjacent Duplicates

In this tutorial, we will write the Python program to remove all adjacent duplicate elements recursively. In this problem, we are given a string and we need to return output string that should not have any adjacent duplicate element. Let's understand the following example.

Example -

Input: bzxxa
Output: ba
First "bzxxa" is reduced to "bzza". 
The string "bzza" contains duplicates, 
so it is further reduced to "ba".

Let's understand the following example.

Method - 1:

Let's understand the following example.

Example -

def remove_adjacent_duplicates(string):
    stack = []  # Using a stack to store non-duplicate characters
    for char in string:
        if stack and char == stack[-1]:
            stack.pop()  # Remove the top element from the stack if it is a duplicate
        else:
            stack.append(char)  # Push the character onto the stack if it is not a duplicate
    return ''.join(stack)  # Convert the stack to a string and return

# Driver code
string1 = "geeksforgeeg"
print(remove_adjacent_duplicates(string1))

string1 = "azxxxzy"
print(remove_adjacent_duplicates(string1))
string2 = "acbbcddc"
print(remove_adjacent_duplicates(string2))

Output:

ay
ac

Explanation -

In the above code, the remove_adjacent_duplicates() function takes a string as input and removes all adjacent duplicates from it. A stack is used to store non-duplicate characters. We iterate over each character in the string.

If the stack is not empty and the current character is equal to the top element of the stack, it means we have found a duplicate character. In such cases, we remove the top element from the stack using the pop() method. If the current character is not a duplicate, we push it onto the stack using the append() method.

After iterating through all the characters, we convert the stack to a string using the ''.join(stack) method and return the resulting string.

Finally, we provide several strings where the remove_adjacent_duplicates() function is called with different strings, and the output is printed.

Method - 2:

Let's understand another approach.

Example -

def remove_adjacent_duplicates(s, ch):
    if len(s) <= 1:
        return s

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

            last_char = s[i - 1] if i > 0 else ch
            rem_str = remove_adjacent_duplicates(s[j + 1:], last_char)

            s = s[:i]
            k, l = len(s), 0

            while len(rem_str) > 0 and len(s) > 0 and rem_str[0] == s[len(s) - 1]:
                while len(rem_str) > 0 and rem_str[0] != ch and rem_str[0] == s[len(s) - 1]:
                    rem_str = rem_str[1:]

                s = s[:-1]

            s += rem_str
            i = j

        else:
            i += 1

    return s
str1 = "mississipie"
print(remove_adjacent_duplicates(str1, ' '))
str2 = "ocvvcolop"
print(remove_adjacent_duplicates(str2, ' '))

Output:

mpie
lop

Explanation -

The remove_adjacent_duplicates() function takes a string s and a character ch as input and recursively removes all adjacent duplicates from the string.

If the length of the string is less than or equal to 1, the function returns the string as is.

The function iterates over the characters in the string using a while loop. If two adjacent characters are the same, it finds the range of consecutive duplicate characters. The function then recursively calls itself with the remaining part of the string after the consecutive duplicates.

The function removes the consecutive duplicates from the current range and appends the remaining string after the duplicates to the updated string.

If there are no consecutive duplicates, the function moves to the next character.

Finally, the function returns the updated string with all the adjacent duplicates removed.

We provides two test cases where the remove_adjacent_duplicates() function is called with different strings and characters, and the output is printed.

Method - 4

We can solve this problem using the regex and run a loop to find the character having length more than 1. Let's understand the following example.

Example -

import re

def remove(s):
    groups = [(match.group() for match in re.finditer(r'(.)\1*', s))]
    s = ''
    for i in groups:
        if len(i) > 1:
            continue
        s += i
    return s

def rremove(s):
    ps = ''
    while len(ps) != len(s):
        ps = s
        s = remove(s)
    return s
str1 = "abccbccba"
print(rremove(str1))

Output:

Explanation -

In the above code, the remove() function uses regular expressions to find groups of consecutive repeated characters in the string s. It iterates over the matches found using re.finditer and stores them in the groups list.

It then checks the length of each group and appends it to the string s if the length is not greater than 1. The rremove() function repeatedly calls the remove function on the input string s until the length of the string s remains unchanged. It updates the previous string ps to store the previous value of s before each iteration.

Finally, it returns the resulting string after removing all adjacent duplicates.

Next TopicWrite the Python Program to Reverse the Vowels in the Given String

← prev next →