Remove all consecutive duplicates from the string using recursion

Remove all consecutive duplicates from the string using sliding window:

Remove all consecutive duplicates from the string using Iterative approach:

Approach:

If the string is not empty compare the adjacent characters of the string. If they are the same then shift the characters one by one to the left. Call recursion on string S otherwise, call recursion from S+1 string.

Follow the below steps to implement the idea:

If the string is empty, return.
Else compare the adjacent characters of the string. If they are the same then shift the characters one by one to the left. Call recursion on string S
If they are not same then call recursion from S+1 string.

Illustration:

The recursion tree for the string S = aabcca is shown below.
aabcca S = aabcca
/
abcca S = abcca
/
bcca S = abcca
/
cca S = abcca
/
ca S = abca
/
a S = abca (Output String)
/
empty string

Below is the implementation of the above approach:

C++

// Recursive Program to remove consecutive
// duplicates from string S.
#include <bits/stdc++.h>
using namespace std;
 
// A recursive function that removes
// consecutive duplicates from string S
void removeDuplicates(char* S)
{
    // When string is empty, return
    if (S[0] == '\0')
        return;
 
    // if the adjacent characters are same
    if (S[0] == S[1]) {
 
        // Shift character by one to left
        int i = 0;
        while (S[i] != '\0') {
            S[i] = S[i + 1];
            i++;
        }
 
        // Check on Updated String S
        removeDuplicates(S);
    }
 
    // If the adjacent characters are not same
    // Check from S+1 string address
    removeDuplicates(S + 1);
}
 
// Driver Program
int main()
{
    char S1[] = "w3wiki";
    removeDuplicates(S1);
    cout << S1 << endl;
 
    char S2[] = "aabcca";
    removeDuplicates(S2);
    cout << S2 << endl;
 
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static String
    removeConsecutiveDuplicates(String input)
    {
        if (input.length() <= 1)
            return input;
        if (input.charAt(0) == input.charAt(1))
            return removeConsecutiveDuplicates(
                input.substring(1));
        else
            return input.charAt(0)
                + removeConsecutiveDuplicates(
                       input.substring(1));
    }
    public static void main(String[] args)
    {
        String S1 = "w3wiki";
        System.out.println(removeConsecutiveDuplicates(S1));
 
        String S2 = "aabcca";
        System.out.println(removeConsecutiveDuplicates(S2));
    }
}

Python3

# Recursive Program to remove consecutive
# duplicates from string S.
 
 
def removeConsecutiveDuplicates(s):
    if len(s) < 2:
        return s
    if s[0] != s[1]:
        return s[0]+removeConsecutiveDuplicates(s[1:])
    return removeConsecutiveDuplicates(s[1:])
 
 
# This code is contributed by direwolf707
s1 = 'w3wiki'
print(removeConsecutiveDuplicates(s1))  # geksforgeks
s2 = 'aabcca'
print(removeConsecutiveDuplicates(s2))  # ab
 
# This code is contributed by rahulsood707.

C#

/*package whatever //do not write package name here */
using System;
 
class GFG {
    public static string
    removeConsecutiveDuplicates(string input)
    {
        if (input.Length <= 1)
            return input;
        if (input[0] == input[1])
            return removeConsecutiveDuplicates(
                input.Substring(1));
        else
            return input[0]
                + removeConsecutiveDuplicates(
                       input.Substring(1));
    }
    public static void Main(String[] args)
    {
        string S1 = "w3wiki";
        Console.WriteLine(removeConsecutiveDuplicates(S1));
 
        string S2 = "aabcca";
        Console.Write(removeConsecutiveDuplicates(S2));
    }
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
 
function removeConsecutiveDuplicates(input)
{
    if(input.length<=1)
            return input;
        if(input[0]==input[1])
            return removeConsecutiveDuplicates(input.substring(1));
        else
            return input[0] + 
            removeConsecutiveDuplicates(input.substring(1));
}
 
let S1 = "w3wiki";
document.write(removeConsecutiveDuplicates(S1)+"<br>");
 
let  S2 = "aabcca";
document.write(removeConsecutiveDuplicates(S2)+"<br>");
 
 
// This code is contributed by rag2127
 
</script>

Output

geksforgeks
abca

Time complexity: O(N²)
Auxiliary Space: O(N)

Remove all consecutive duplicates from the string

Given a string S, The task is to remove all the consecutive duplicate characters of the string and return the resultant string.

Note: that this problem is different from Recursively remove all adjacent duplicates. Here we keep one character and remove all subsequent same characters.

Examples:

Input: S= “aaaaabbbbbb”
Output: ab

Input: S = “w3wiki”
Output: geksforgeks

Input: S = “aabccba”
Output: abcba

Tags:

#DSA #Strings #Strings