Recursively remove all adjacent duplicates
Given a string, recursively remove adjacent duplicate characters from the string. The output string should not have any adjacent duplicates. See the following examples.
Examples:
Input: azxxzy
Output: ay
- First “azxxzy” is reduced to “azzy”.
- The string “azzy” contains duplicates,
- so it is further reduced to “ay”.
Input: Beginnerforgeeg
Output: gksfor
- First “Beginnerforgeeg” is reduced to “gksforgg”.
- The string “gksforgg” contains duplicates,
- so it is further reduced to “gksfor”.
Input: caaabbbaacdddd
Output: Empty StringInput: acaaabbbacdddd
Output: acac
The following approach can be followed to remove duplicates in O(N) time:
- Start from the leftmost character and remove duplicates at left corner if there are any.
- The first character must be different from its adjacent now. Recur for string of length n-1 (string without first character).
- Let the string obtained after reducing right substring of length n-1 be rem_str. There are three possible cases
- If first character of rem_str matches with the first character of original string, remove the first character from rem_str.
- If remaining string becomes empty and last removed character is same as first character of original string. Return empty string.
- Else, append the first character of the original string at the beginning of rem_str.
- Return rem_str.
Below image is a dry run of the above approach:
Below is the implementation of the above approach:
// C++ program to remove all adjacent duplicates from a
// string
#include <bits/stdc++.h>
using namespace std;
// Recursively removes adjacent duplicates from str and
// returns new string. last_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 definitely
// 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[] = "Beginnerforgeeg";
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;
}
// This code is contributed by Aditya Kumar (adityakumar129)
// C program to remove all adjacent duplicates from a string
#include <stdio.h>
#include <string.h>
// Recursively removes adjacent duplicates from str and
// returns new string. last_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 definitely
// 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* removes(char* str)
{
char last_removed = '\0';
return removeUtil(str, &last_removed);
}
// Driver program to test above functions
int main()
{
char str1[] = "Beginnerforgeeg";
printf("%s\n", removes(str1));
char str2[] = "azxxxzy";
printf("%s\n", removes(str2));
char str3[] = "caaabbbaac";
printf("%s\n", removes(str3));
char str4[] = "gghhg";
printf("%s\n", removes(str4));
char str5[] = "aaaacddddcappp";
printf("%s\n", removes(str5));
char str6[] = "aaaaaaaaaa";
printf("%s\n", removes(str6));
char str7[] = "qpaaaaadaaaaadprq";
printf("%s\n", removes(str7));
char str8[] = "acaaabbbacdddd";
printf("%s\n", removes(str8));
char str9[] = "acbbcddc";
printf("%s\n", removes(str9));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
// Java program to remove all adjacent duplicates from a
// string
import java.io.*;
import java.util.*;
class GFG {
static char last_removed; // will store the last char
// removed during recursion
// Recursively removes adjacent duplicates from str and
// returns new string. last_removed is a pointer to
// last_removed character
static String removeUtil(String str)
{
// 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);
}
// At this point, the first character is definitely
// different from its adjacent. Ignore first
// character and recursively remove characters from
// remaining string
String rem_str
= removeUtil(str.substring(1, str.length()));
// 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)
{
last_removed = '\0';
return removeUtil(str);
}
// Driver code
public static void main(String args[])
{
String str1 = "Beginnerforgeeg";
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 contributed by Aditya Kumar (adityakumar129)
# Python program to remove
# all adjacent duplicates from a string
# Recursively removes adjacent
# duplicates from str and returns
# new string. last_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 definitely 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 = "Beginnerforgeeg"
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
// C# program to remove
// all adjacent duplicates
// from a string
using System;
class GFG {
// Recursively removes adjacent
// duplicates from str and returns
// new string. last_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[0] == str[1]) {
last_removed = str[0];
while (str.Length > 1 && str[0] == str[1]) {
str = str.Substring(1, str.Length - 1);
}
str = str.Substring(1, str.Length - 1);
return removeUtil(str, last_removed);
}
// At this point, the first
// character is definitely different
// from its adjacent. Ignore first
// character and recursively
// remove characters from remaining string
string rem_str = removeUtil(
str.Substring(1, str.Length - 1), 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[0] == str[0]) {
last_removed = str[0];
// Remove first character
return rem_str.Substring(1, rem_str.Length - 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.Length == 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
return (str[0] + rem_str);
}
static string remove(string str)
{
char last_removed = '\0';
return removeUtil(str, last_removed);
}
// Driver code
public static void Main()
{
string str1 = "Beginnerforgeeg";
Console.Write(remove(str1) + "\n");
string str2 = "azxxxzy";
Console.Write(remove(str2) + "\n");
string str3 = "caaabbbaac";
Console.Write(remove(str3) + "\n");
string str4 = "gghhg";
Console.Write(remove(str4) + "\n");
string str5 = "aaaacddddcappp";
Console.Write(remove(str5) + "\n");
string str6 = "aaaaaaaaaa";
Console.Write(remove(str6) + "\n");
string str7 = "qpaaaaadaaaaadprq";
Console.Write(remove(str7) + "\n");
string str8 = "acaaabbbacdddd";
Console.Write(remove(str8) + "\n");
string str9 = "acbbcdd";
Console.Write(remove(str9) + "\n");
}
}
// This code is contributed by Samim Hossain Mondal.
// Javascript program to remove
// all adjacent duplicates from a string
// Recursively removes adjacent
// duplicates from str and returns
// new string. last_removed is a
// pointer to last_removed character
function removeUtil(string, last_removed){
// If length of string is 1 or 0
if(string.length == 0 || string.length == 1)
return string
// Remove leftmost same characters
// and recur for remaining
// string
if(string[0] == string[1]){
last_removed = string.charCodeAt(0)
while(string.length > 1 && string[0] == string[1])
string = string.substr(1,)
string = string.substr(1,)
return removeUtil(string, last_removed)
}
// At this point, the first
// character is functionality different
// from its adjacent. Ignore first
// character and recursively
// remove characters from remaining string
let rem_str = removeUtil(string.substr(1,), 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[0] == string[0]){
last_removed = string.charCodeAt(0)
return rem_str.substr(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.length == 0 && last_removed == string.charCodeAt(0))
return rem_str
// If the two first characters of
// str and rem_str don't match,
// push first character of str
// before the first character of
// rem_str.
let res = string[0] + rem_str
return res
}
function remove(string){
let last_removed = 0
return removeUtil(string,last_removed)
}
// Driver program
let string1 = "Beginnerforgeeg"
console.log(remove(string1),"</br>")
let string2 = "azxxxzy"
console.log(remove(string2),"</br>")
let string3 = "caaabbbaac"
console.log(remove(string3),"</br>")
let string4 = "gghhg"
console.log(remove(string4),"</br>")
let string5 = "aaaacddddcappp"
console.log(remove(string5),"</br>")
let string6 = "aaaaaaaaaa"
console.log(remove(string6),"</br>")
let string7 = "qpaaaaadaaaaadprq"
console.log(remove(string7),"</br>")
let string8 = "acaaabbbacdddd"
console.log(remove(string8),"</br>")
let string9 = "acbbcddc"
console.log(remove(string9),"</br>")
// This code is contributed by shinjanpatra
Output
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 length of the input string and k is the number of first characters which are same. Solution of the recurrence is O(n)
Auxiliary Space: O(n)
Thanks to Prachi Bodke for suggesting this problem and initial solution.
Another Approach:
The idea here is to check whether the String remStr has the repeated character that matches the last char of the parent String. If that is happening then we have to keep removing that character before concatenating string s and string remStr.
Below is the implementation of the above approach:
// C++ Program for above approach
#include <bits/stdc++.h>
using namespace std;
// Recursively removes adjacent
// duplicates from str and
// returns new string. las_removed
// is a pointer to
// last_removed character
string removeDuplicates(string s, char ch)
{
// If length of string is 1 or 0
if (s.length() <= 1) {
return s;
}
int i = 0;
while (i < s.length()) {
if (i + 1 < s.length() && s[i] == s[i + 1]) {
int j = i;
while (j + 1 < s.length() && s[j] == s[j + 1]) {
j++;
}
char lastChar = i > 0 ? s[i - 1] : ch;
string remStr = removeDuplicates(
s.substr(j + 1, s.length()), lastChar);
s = s.substr(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[0] == s[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[0] != ch
&& remStr[0] == s[s.length() - 1]) {
remStr
= remStr.substr(1, remStr.length());
}
s = s.substr(0, s.length() - 1);
}
s = s + remStr;
i = j;
}
else {
i++;
}
}
return s;
}
// Driver Code
int main()
{
string str1 = "mississipie";
cout << removeDuplicates(str1, ' ') << endl;
string str2 = "ocvvcolop";
cout << removeDuplicates(str2, ' ') << endl;
}
// This code is contributed by nirajgusain5
// Java Program for above approach
import java.io.*;
import java.lang.*;
import java.util.*;
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 contributed by Niharika Sahai
# Python Program for above approach
# Recursively removes adjacent
# duplicates from str and
# returns new string. las_removed
# is a pointer to
# last_removed character
def removeDuplicates(s, ch):
# If length of string is 1 or 0
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
lastChar = s[i - 1] if(i > 0) else ch
remStr = removeDuplicates(s[j + 1: len(s)], lastChar)
s = s[0: i]
k, l = len(s), 0
# Recursively remove all the adjacent
# characters formed by removing the
# adjacent characters
while (len(remStr) > 0 and len(s) > 0
and remStr[0] == s[len(s) - 1]):
# Have to check whether this is the
# repeated character that matches the
# last char of the parent String
while (len(remStr) > 0
and remStr[0] != ch
and remStr[0] == s[len(s) - 1]):
remStr = remStr[1: len(remStr)+1]
s = s[0: len(s) - 1]
s = s + remStr
i = j
else:
i += 1
return s
# Driver Code
str1 = "mississipie"
print(removeDuplicates(str1, ' '))
str2 = "ocvvcolop"
print(removeDuplicates(str2, ' '))
# This code is contributed by shinjanpatra
using System;
class HelloWorld {
// Recursively removes adjacent
// duplicates from str and
// returns new string. las_removed
// is a pointer to
// last_removed character
static string removeDuplicates(string s, char ch)
{
// If length of string is 1 or 0
if (s.Length <= 1) {
return s;
}
int i = 0;
while (i < s.Length) {
if (i + 1 < s.Length && s[i] == s[i + 1]) {
int j = i;
while (j + 1 < s.Length
&& s[j] == s[j + 1]) {
j++;
}
char lastChar = i > 0 ? s[i - 1] : ch;
// Console.Write(j+ " here " );
string remStr = removeDuplicates(
s.Substring(j + 1, s.Length - j - 1),
lastChar);
s = s.Substring(0, i);
int k = s.Length;
// Recursively remove all the adjacent
// characters formed by removing the
// adjacent characters
while (remStr.Length > 0 && s.Length > 0
&& remStr[0] == s[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[0] != ch
&& remStr[0] == s[s.Length - 1]) {
remStr = remStr.Substring(
1, remStr.Length - 1);
}
s = s.Substring(0, s.Length - 1);
}
s = s + remStr;
i = j;
}
else {
i++;
}
}
return s;
}
static void Main()
{
string str1 = "mississipie";
Console.WriteLine(removeDuplicates(str1, ' '));
string str2 = "ocvvcolop";
Console.WriteLine(removeDuplicates(str2, ' '));
}
}
// This code is contributed by garg28harsh.
// JavaScript Program for above approach
// Recursively removes adjacent
// duplicates from str and
// returns new string. las_removed
// is a pointer to
// last_removed character
function removeDuplicates(s,ch)
{
// If length of string is 1 or 0
if (s.length <= 1) {
return s;
}
let i = 0;
while (i < s.length) {
if (i + 1 < s.length && s[i] == s[i + 1]) {
let j = i;
while (j + 1 < s.length && s[j] == s[j + 1]) {
j++;
}
let lastChar = i > 0 ? s[i - 1] : ch;
let remStr = removeDuplicates(
s.substring(j + 1, s.length), lastChar);
s = s.substring(0, i);
let 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[0] == s[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[0] != ch
&& remStr[0] == s[s.length - 1]) {
remStr
= remStr.substring(1, remStr.length+1);
}
s = s.substring(0, s.length - 1);
}
s = s + remStr;
i = j;
}
else {
i++;
}
}
return s;
}
// Driver Code
let str1 = "mississipie";
console.log(removeDuplicates(str1, ' '));
let str2 = "ocvvcolop";
console.log(removeDuplicates(str2, ' '),"</br>");
// This code is contributed by shinjanpatra
Output
mpie lop
Time Complexity: O(n2), as substr method takes o(n) time, so the complexity will be O(n2).
Auxiliary Space: O(n2), as a substring copy of the original string is passed in the recursive function.
Another Approach:
The idea here is to find the duplicate characters using regular expression and run a loop to find the characters having length more than 1. If the resultant string still needs improvement then we will call the function again with the resultant string as a parameter. Here our ps would be having previous string and s would be having new string. If both are equal we will break the loop and return the answer.
#include<bits/stdc++.h>
#include<string>
#include<regex>
using namespace std;
string remove(string s)
{
smatch match;
string str;
while(regex_search(s,match, regex(R"((.)\1*)")))
{
if(match.str().size() > 1)
{
s=match.suffix().str();
}
else
{
str+=match.str();
s=match.suffix().str();
}
}
return str;
}
string rremove(string s)
{
string temp;
while(s.size() != temp.size())
{
temp = s;
s = remove(s);
}
return s;
}
int main()
{
string str1 = "Beginnerforgeek";
cout<<rremove(str1)<<endl;
string str2 = "abccbccba";
cout<<rremove(str2)<<endl;
return 0;
}
// This code is contributed by factworx412
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
public static void main(String[] args)
{
String str1 = "Beginnerforgeek";
System.out.println(rremove(str1));
String str2 = "abccbccba";
System.out.println(rremove(str2));
}
public static String remove(String s)
{
Pattern pattern = Pattern.compile("(.)\\1*");
Matcher matcher = pattern.matcher(s);
String str = "";
while (matcher.find()) {
if (matcher.group().length() > 1) {
s = matcher.replaceFirst("");
matcher = pattern.matcher(s);
}
else {
str += matcher.group();
s = matcher.replaceFirst("");
matcher = pattern.matcher(s);
}
}
return str;
}
public static String rremove(String s)
{
String temp;
while (s.length() != (temp = remove(s)).length()) {
s = temp;
}
return s;
}
}
// This code is contributed by Tapesh(tapeshdua420)
# code
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
# Driver Code
str1 = "Beginnerforgeek"
print(rremove(str1))
str2 = "abccbccba"
print(rremove(str2))
using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
class Program {
static void Main(string[] args)
{
string str1 = "Beginnerforgeek";
Console.WriteLine(rremove(str1));
string str2 = "abccbccba";
Console.WriteLine(rremove(str2));
Console.ReadKey();
}
static string remove(string s)
{
MatchCollection match;
string str = "";
while (Regex.IsMatch(s, @"(.)\1*")) {
match = Regex.Matches(s, @"(.)\1*");
if (match[0].Length > 1) {
s = s.Substring(match[0].Length);
}
else {
str += match[0].Value;
s = s.Substring(match[0].Length);
}
}
return str;
}
static string rremove(string s)
{
string temp;
while (s.Length != (temp = remove(s)).Length) {
s = temp;
}
return s;
}
}
// This code is contributed by Tapesh(tapeshdua420)
function remove(s)
{
// Find all consecutive identical characters in the input string
const groups = s.match(/(.)\1*/g) || [];
let result = '';
for (const group of groups) {
if (group.length > 1) {
continue;
}
result += group;
}
return result;
}
function rremove(s) {
let prevStr = '';
// Keep removing consecutive identical
// characters until the input string no longer changes
while (prevStr !== s) {
prevStr = s;
s = remove(s);
}
return s;
}
// Driver Code
const str1 = "Beginnerforgeek";
console.log(rremove(str1)); // "gksforgk"
const str2 = "abccbccba";
console.log(rremove(str2));
Output
gksforgk
Time Complexity: O(n), as remove() is taking only O(n) time, so the complexity would be O(n).
Auxiliary Space: O(n2), as groups and ps is taking O(n) space and O(n) is used for function recursion stack (Auxiliary Space).
Another Approach:
To solve this problem, we can utilize a stack data structure and recursion. The idea is to traverse the string from left to right and maintain a stack to store the characters. Whenever we encounter a character that is the same as the top of the stack, we remove both the character from the stack and the character from the string. This process continues until there are no more adjacent duplicates.
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm> // Include the algorithm header for reverse
class GFG {
public:
static std::string rremove(std::string S) {
std::vector<char> newString(S.begin(), S.end()); // Convert the string to a vector of characters
std::stack<char> stack; // Initialize an empty stack
int i = 0; // Initialize the index variable
while (i < S.length()) {
// Check if stack is not empty and top of stack is the same as S[i]
if (!stack.empty() && stack.top() == S[i]) {
// Remove consecutive characters equal to the top of the stack
while (i < S.length() && S[i] == stack.top()) {
i++;
}
stack.pop();
}
// If S[i] is different from top of the stack, push it onto the stack
if (i < S.length()) {
stack.push(S[i]);
i++;
}
}
// Check if resulting string is the same as the original string
std::vector<char> stackVector;
while (!stack.empty()) {
stackVector.push_back(stack.top());
stack.pop();
}
std::reverse(stackVector.begin(), stackVector.end());
if (newString == stackVector) {
return std::string(newString.begin(), newString.end()); // Return the resulting string
} else {
std::string result(stackVector.begin(), stackVector.end());
return rremove(result); // Recursively call rremove with the resulting string as input
}
}
};
int main() {
std::string inputString = "w3wikis";
// Function call
std::string outputString = GFG::rremove(inputString);
std::cout << "Output: " << outputString << std::endl;
return 0;
}
// Contributed by Siddhesh
import java.util.*;
public class GFG {
public static String rremove(String S) {
char[] newString = S.toCharArray(); // Convert the string to a char array
Stack<Character> stack = new Stack<>(); // Initialize an empty stack
int i = 0; // Initialize the index variable
while (i < S.length()) {
// Check if stack is not empty and top of stack is the same as S[i]
if (!stack.isEmpty() && stack.peek() == S.charAt(i)) {
// Remove consecutive characters equal to the top of the stack
while (i < S.length() && S.charAt(i) == stack.peek()) {
i++;
}
stack.pop();
}
// If S[i] is different from top of the stack, push it onto the stack
if (i < S.length()) {
stack.push(S.charAt(i));
i++;
}
}
// Check if resulting string is the same as the original string
char[] stackArray = new char[stack.size()];
for (int j = 0; j < stackArray.length; j++) {
stackArray[j] = stack.get(j);
}
if (Arrays.equals(newString, stackArray)) {
StringBuilder result = new StringBuilder();
for (char c : newString) {
result.append(c);
}
return result.toString(); // Return the resulting string
} else {
StringBuilder result = new StringBuilder();
for (char c : stackArray) {
result.append(c);
}
return rremove(result.toString()); // Recursively call rremove with the resulting string as input
}
}
public static void main(String[] args) {
String inputString = "w3wikis";
// Function call
String outputString = rremove(inputString);
System.out.println("Output: " + outputString);
}
}
class Solution:
def rremove(self, S):
new = [i for i in S] # Convert the string to a list
st = [] # Initialize an empty stack
i = 0 # Initialize the index variable
while i < len(S):
# Check if stack is not empty and top of stack is the same as S[i]
if st and st[-1] == S[i]:
# Remove consecutive characters equal to the top of the stack
while i < len(S) and S[i] == st[-1]:
i += 1
st.pop()
# If S[i] is different from top of the stack, push it onto the stack
if i < len(S):
st.append(S[i])
i += 1
# Check if resulting string is the same as original string
if new == st:
return ''.join(new) # Return the resulting string
# Recursively call rremove with the resulting string as input
else:
return self.rremove(''.join(st))
# Example usage:
s = Solution()
input_string = "w3wikis"
# Function call
output_string = s.rremove(input_string)
print("Output:", output_string)
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
public static string RRemove(string S)
{
List<char> newString = S.ToList(); // Convert the string to a list of characters
Stack<char> stack = new Stack<char>(); // Initialize an empty stack
int i = 0; // Initialize the index variable
while (i < S.Length)
{
// Check if stack is not empty and top of stack is the same as S[i]
if (stack.Count > 0 && stack.Peek() == S[i])
{
// Remove consecutive characters equal to the top of the stack
while (i < S.Length && S[i] == stack.Peek())
{
i++;
}
stack.Pop();
}
// If S[i] is different from top of the stack, push it onto the stack
if (i < S.Length)
{
stack.Push(S[i]);
i++;
}
}
// Check if resulting string is the same as the original string
List<char> stackList = stack.ToList();
stackList.Reverse();
if (newString.SequenceEqual(stackList))
{
return new string(newString.ToArray()); // Return the resulting string
}
else
{
string result = new string(stackList.ToArray());
return RRemove(result); // Recursively call RRemove with the resulting string as input
}
}
}
class Program
{
static void Main()
{
string inputString = "w3wikis";
// Function call
string outputString = GFG.RRemove(inputString);
Console.WriteLine("Output: " + outputString);
}
}
class Solution {
rremove(S) {
// Convert the string to a list
let ne = Array.from(S);
// Initialize an empty stack
let st = [];
// Initialize the index variable
let i = 0;
while (i < S.length) {
// Check if stack is not empty and top of stack is the same as S[i]
if (st.length && st[st.length - 1] === S[i]) {
// Remove consecutive characters equal to the top of the stack
while (i < S.length && S[i] === st[st.length - 1]) {
i += 1;
}
st.pop();
}
// If S[i] is different from top of the stack, push it onto the stack
if (i < S.length) {
st.push(S[i]);
i += 1;
}
}
// Check if resulting string is the same as original string
if (ne.join('') === st.join('')) {
return ne.join('');
}
// Recursively call rremove with the resulting string as input
else {
return this.rremove(st.join(''));
}
}
}
// Test case
let s = new Solution();
let input_string = "w3wikis";
let output_string = s.rremove(input_string);
console.log("Output:", output_string);
Output
Output: gksforgk
Time Complexity Analysis:
The time complexity of this code is O(n), where n is the length of the input string S. This is because we traverse the string once using the while loop, and each character is processed only once.
Space Complexity Analysis:
The space complexity of this code is O(n), where n is the length of the input string S. The space is mainly used to store the characters in the stack and the resulting string.
Contact Us