Recursive Algorithm for Removing Adjacent Duplicates

Given a string, recursively removes adjacent duplicate characters from the string. The output string should not contain any adjacent duplicates. See the example below.

Example:

Input: azxxzy
Output: ay
first reduce “azxxzy” to “azzy”. The string “azzy” contains duplicates, so it is further simplified to “ay”.
Input: geeksforgeeg
Output: gksfor
The first “geeksforgeeg” is simplified to “gksforgg”. The string “gksforgg” contains duplicates, so it is further simplified to “gksfor”.
Input: caaabbbaacddddd
Output: Empty string
Input: acaaabbbacdddddd
Output: acac

The following methods can be followed to remove duplicates on time:

Start with the leftmost character, and if there are duplicates, remove the duplicates in the upper left corner.
The first character must be different from the first character now. Repeat strings of length n-1 (strings that do not contain the first character).
The string obtained by reducing the right substring of length n-1 is rem_str. There are three possible scenarios
1. If it is the first character rem_str it matches the first character of the original string, remove the first character from rem_str.
2. If the remaining string is empty, and the last deleted character is the same as the first character of the original string. Returns an empty string.
3. Otherwise, add the first character of the original string to the rem_str.
Back to rem_str.

The following diagram is a simulation of the above method:

Here’s an implementation of the above method:

Table of Contents

C++

//C/C++ program to remove all
//adjacent duplicates from a string
#include <iostream>
#include <string.h>
 
using namespace std;
 
//Recursively removes adjacent
//duplicates from str and returns
//new string. las_removed is a
//pointer to last_removed character
char * removeUtil( char *str, char *last_removed)
{
     
     //If length of string is 1 or 0
     if (str[0] == '\0' || str[1] == '\0' )
         return str;
 
     //Remove leftmost same characters
     //and recur for remaining
     //string
     if (str[0] == str[1])
     {
         *last_removed = str[0];
         while (str[1] && str[0] == str[1])
             str++;
         str++;
         return removeUtil(str, last_removed);
     }
 
     //At this point, the first character
     //is definiotely different
     //from its adjacent. Ignore first
     //character and recursively
     //remove characters from remaining string
     char * rem_str = removeUtil(str+1, last_removed);
 
     //Check if the first character
     //of the rem_string matches with
     //the first character of the
     //original string
     if (rem_str[0] && rem_str[0] == str[0])
     {
         *last_removed = str[0];
       
         //Remove first character
         return (rem_str+1);
     }
 
     //If remaining string becomes
     //empty and last removed character
     //is same as first character of
     //original string. This is needed
     //for a string like "acbbcddc"
     if (rem_str[0] == '\0' &&
                  *last_removed == str[0])
         return rem_str;
 
     //If the two first characters
     //of str and rem_str don't match, //append first character of str
     //before the first character of
     //rem_str.
     rem_str--;
     rem_str[0] = str[0];
     return rem_str;
}
 
//Function to remove
char * remove ( char *str)
{
     char last_removed = '\0' ;
     return removeUtil(str, &last_removed);
}
 
//Driver program to test
//above functions
int main()
{
     char str1[] = "geeksforgeeg" ;
     cout <<remove (str1) <<endl;
 
     char str2[] = "azxxxzy" ;
     cout <<remove (str2) <<endl;
 
     char str3[] = "caaabbbaac" ;
     cout <<remove (str3) <<endl;
 
     char str4[] = "gghhg" ;
     cout <<remove (str4) <<endl;
 
     char str5[] = "aaaacddddcappp" ;
     cout <<remove (str5) <<endl;
 
     char str6[] = "aaaaaaaaaa" ;
     cout <<remove (str6) <<endl;
 
     char str7[] = "qpaaaaadaaaaadprq" ;
     cout <<remove (str7) <<endl;
 
     char str8[] = "acaaabbbacdddd" ;
     cout <<remove (str8) <<endl;
 
     char str9[] = "acbbcddc" ;
     cout <<remove (str9) <<endl;
 
     return 0;
}

Java

//Java program to remove
//all adjacent duplicates
//from a string
import java.io.*;
import java.util.*;
 
class GFG
{
   
   //Recursively removes adjacent
   // duplicates from str and returns
   //new string. las_removed is a
   //pointer to last_removed character
   static String removeUtil(String str, char last_removed)
   {
     
     //If length of string is 1 or 0
     if (str.length() == 0 || str.length() == 1 )
       return str;
 
     //Remove leftmost same characters
     //and recur for remaining 
     //string
     if (str.charAt( 0 ) == str.charAt( 1 ))
     {
       last_removed = str.charAt( 0 );
       while (str.length()> 1 && str.charAt( 0 ) ==
                                    str.charAt( 1 ))
         str = str.substring( 1 , str.length());
       str = str.substring( 1 , str.length());
       return removeUtil(str, last_removed);
     }
 
     //At this point, the first
     //character is definiotely different 
     //from its adjacent. Ignore first
     //character and recursively 
     //remove characters from remaining string
     String rem_str = removeUtil(str.substring(
                   1 , str.length()), last_removed);
 
     //Check if the first character of
     //the rem_string matches with 
     //the first character of the original string
     if (rem_str.length() != 0 &&
              rem_str.charAt( 0 ) == str.charAt( 0 ))
     {
       last_removed = str.charAt( 0 );
       
       //Remove first character
       return rem_str.substring( 1 , rem_str.length());
     }
 
     //If remaining string becomes
     //empty and last removed character
     //is same as first character of
     //original string. This is needed
     //for a string like "acbbcddc"
     if (rem_str.length() == 0 && last_removed ==
                                       str.charAt( 0 ))
       return rem_str;
 
     //If the two first characters
     //of str and rem_str don't match, //append first character of str
     //before the first character of
     //rem_str
     return (str.charAt( 0 ) + rem_str);
   }
 
   static String remove(String str) 
   {
     char last_removed = '\0' ;
     return removeUtil(str, last_removed);      
   }
 
   //Driver code
   public static void main(String args[])
   {
     String str1 = "geeksforgeeg" ;
     System.out.println(remove(str1));
 
     String str2 = "azxxxzy" ;
     System.out.println(remove(str2));
 
     String str3 = "caaabbbaac" ;
     System.out.println(remove(str3));
 
     String str4 = "gghhg" ;
     System.out.println(remove(str4));
 
     String str5 = "aaaacddddcappp" ;
     System.out.println(remove(str5));
 
     String str6 = "aaaaaaaaaa" ;
     System.out.println(remove(str6));
 
     String str7 = "qpaaaaadaaaaadprq" ;
     System.out.println(remove(str7));
 
     String str8 = "acaaabbbacdddd" ;
     System.out.println(remove(str8));
   }
}
 
//This code is contibuted by rachana soma

Python

# Python program to remove
# all adjacent duplicates from a string
 
# Recursively removes adjacent
# duplicates from str and returns
# new string. las_removed is a
# pointer to last_removed character
def removeUtil(string, last_removed):
 
     # If length of string is 1 or 0
     if len (string) = = 0 or len (string) = = 1 :
         return string
 
     # Remove leftmost same characters
     # and recur for remaining
     # string
     if string[ 0 ] = = string[ 1 ]:
         last_removed = ord (string[ 0 ])
         while len (string)> 1 and string[ 0 ] = =
                                     string[ 1 ]:
             string = string[ 1 :]
         string = string[ 1 :]
 
         return removeUtil(string, last_removed)
 
     # At this point, the first
     # character is definiotely different
     # from its adjacent. Ignore first
     # character and recursively
     # remove characters from remaining string
     rem_str = removeUtil(string[ 1 :], last_removed)
 
     # Check if the first character
     # of the rem_string matches
     # with the first character of
     # the original string
     if len (rem_str) ! = 0 and rem_str[ 0 ] = =
                                          string[ 0 ]:
         last_removed = ord (string[ 0 ])
         return (rem_str[ 1 :])
 
     # If remaining string becomes
     # empty and last removed character
     # is same as first character of
     # original string. This is needed
     # for a string like "acbbcddc"
     if len (rem_str) = = 0 and last_removed = =
                                    ord (string[ 0 ]):
         return rem_str
 
     # If the two first characters of
     # str and rem_str don't match, # append first character of str
     # before the first character of
     # rem_str.
     return ([string[ 0 ]] + rem_str)
 
def remove(string):
     last_removed = 0
     return toString(removeUtil(toList(string), last_removed))
 
# Utility functions
def toList(string):
     x = []
     for i in string:
         x.append(i)
     return x
 
def toString(x):
     return ''.join(x)
 
# Driver program
string1 = "geeksforgeeg"
print remove(string1)
 
string2 = "azxxxzy"
print remove(string2)
 
string3 = "caaabbbaac"
print remove(string3)
 
string4 = "gghhg"
print remove(string4)
 
string5 = "aaaacddddcappp"
print remove(string5)
 
string6 = "aaaaaaaaaa"
print remove(string6)
 
string7 = "qpaaaaadaaaaadprq"
print remove(string7)
 
string8 = "acaaabbbacdddd"
print remove(string8)
 
string9 = "acbbcddc"
print remove(string9)
 
# This code is contributed by BHAVYA JAIN

The output is as follows:

gksfor
ay

g
a

qrq
acac
a

Time Complexity:

The time complexity of the solution can be written as T(n) = T(n-k) + O(k), where n is the length of the input string and k is the number of the same first character. The recursive solution is O(n)

Another way:

The idea here is to check if the String remStr has a duplicate character that matches the last character of the parent String. If this happens, then we must proceed to remove the character before concatenating the string s and the string remStr.

Here’s an implementation of the above method:

Java

//Java Program for above approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
 
   //Recursively removes adjacent
   //duplicates from str and
   //returns new string. las_removed
   //is a pointer to
   //last_removed character
   private static String removeDuplicates(
     String s, char ch)
   {
 
     //If length of string is 1 or 0
     if (s == null || s.length() <= 1 )
     {
       return s;
     }
 
     int i = 0 ;
     while (i <s.length())
     {
       if (i + 1 <s.length()
           && s.charAt(i) == s.charAt(i + 1 ))
       {
         int j = i;
         while (j + 1 <s.length()
                && s.charAt(j) ==
                s.charAt(j + 1 ))
         {
           j++;
         }
         char lastChar
           = i> 0 ? s.charAt(i - 1 ) : ch;
 
         String remStr = removeDuplicates(
           s.substring(j + 1 , s.length()), lastChar);
 
         s = s.substring( 0 , i);
         int k = s.length(), l = 0 ;
 
         //Recursively remove all the adjacent
         //characters formed by removing the
         //adjacent characters
         while (remStr.length()> 0 &&
                s.length()> 0 &&
                remStr.charAt( 0 ) ==
                s.charAt(s.length() - 1 ))
         {
 
           //Have to check whether this is the
           //repeated character that matches the
           //last char of the parent String
           while (remStr.length()> 0
                  && remStr.charAt( 0 ) != ch
                  && remStr.charAt( 0 )
                  == s.charAt(s.length()
                              - 1 ))
           {
             remStr = remStr.substring(
               1 , remStr.length());
           }
           s = s.substring( 0 , s.length() - 1 );
         }
         s = s + remStr;
         i = j;
       }
       else
       {
         i++;
       }
     }
     return s;
   }
 
   //Driver Code
   public static void main(String[] args)
   {
 
     String str1 = "mississipie" ;
     System.out.println(removeDuplicates(
       str1, ' ' ));
     String str2 = "ocvvcolop" ;
     System.out.println(removeDuplicates(
       str2, ' ' ));
   }
}
 
//This code is contibuted by Niharika Sahai

The output is as follows:

mpie
lop

Time Complexity: O(n)

Suggest this problem and the initial solution. If you find anything incorrect, or would like to share more information about the above topics, please leave a comment.

Data Structures and Algorithms, IT Technology

Recursive Algorithm for Removing Adjacent Duplicates

C++

Java

Python

Java

Thao Nguyen