Remove all adjacent duplicate characters using recursion

The problem is to remove all adjacent duplicate characters from a given string using recursion. An adjacent duplicate character is a character that appears consecutively more than once in the string. The task is to remove such adjacent duplicates and return the modified string.

Explanation using Example

Let's consider the test cases from the provided code:

1. Test Case 1: Given Text = "apple" After removing adjacent duplicate characters, the modified string is "ale".

2. Test Case 2: Given Text = "xxyyyyx" After removing adjacent duplicate characters, the modified string is "x".

3. Test Case 3: Given Text = "xxyyyxx" After removing adjacent duplicate characters, the modified string is an empty string ("").

4. Test Case 4: Given Text = "xyyxxyx" After removing adjacent duplicate characters, the modified string is "xyx".

5. Test Case 5: Given Text = "xxxxyyyzyyzzxxx" After removing adjacent duplicate characters, the modified string is "z".

6. Test Case 6: Given Text = "xyzzyxy" After removing adjacent duplicate characters, the modified string is "y".

7. Test Case 7: Given Text = "xyxxyx" After removing adjacent duplicate characters, the modified string is an empty string ("").

Pseudocode

``````removeAdjacentDuplicate(text)
if text length is 0
return text
size = text length - 1
auxiliary = size
result = ""
while size >= 0
while size >= 0 and text[auxiliary] == text[size]
size--
if size + 1 == auxiliary
result = text[auxiliary] + result
else
auxiliary = size
return result

print "Given Text : text"
``````

Algorithm Explanation

The `removeAdjacentDuplicate` function is a recursive algorithm to remove all adjacent duplicate characters from the given text using the following steps:

1. If the length of the `text` is 0, it means there are no more characters to process, and the function returns the `text` as it is.
2. The algorithm uses two pointers, `size` and `auxiliary`, both initialized to the last index of the `text`.
3. The algorithm defines an empty string `result` to store the modified text without adjacent duplicates and a boolean variable `task` to indicate whether any adjacent duplicates have been removed.
4. The algorithm enters a loop that iterates until `size` becomes less than 0.
5. Inside the loop, the algorithm checks if the character at index `auxiliary` is equal to the character at index `size`. If they are the same, it means adjacent duplicates are found, and the `size` pointer moves back to the previous character.
6. If `size + 1` is equal to `auxiliary`, it means no adjacent duplicates were found, and the character at index `auxiliary` is added to the beginning of the `result` string.
7. If adjacent duplicates were found, the `task` variable is set to true to indicate that the `text` is modified.
8. The `auxiliary` pointer is updated to the current `size`.
9. After the loop, the algorithm checks if any modifications were made (`task == true`). If so, it recursively calls itself with the `result` as the new `text`.
10. If no modifications were made, the algorithm returns the `result`.

The `removeAdjacent` function handles the request to remove adjacent duplicates from the given text. It first prints the given text and then prints the modified text obtained from the `removeAdjacentDuplicate` function.

Code Solution

Here given code implementation process.

``````/*
Java Program for
Remove all adjacent duplicate characters using recursion
*/
public class RemoveCharacters
{
// Recursively, removing the all adjacent similar characters
{
if (text.length() == 0)
{
return text;
}
// Define some auxiliary variable
int size = text.length() - 1;
int auxiliary = size;
String result = "";
// Execute loop until when size is less than zero
while (size >= 0)
{
while (size >= 0 && text.charAt(auxiliary) == text.charAt(size))
{
size--;
}
if (size + 1 == auxiliary)
{
// When adjacent are not same
// Then add new character at beginning of result
result = text.charAt(auxiliary) + result;
}
else
{
// This is indicate string is modified
}
// Get new index
auxiliary = size;
}
{
}
return result;
}
// Handles the request to printing calculate result
{
System.out.println(" Given Text : " + text);
System.out.println(" Output     : " + removeAdjacentDuplicate(text));
}
public static void main(String[] args)
{
RemoveCharacters test = new RemoveCharacters();
// Test Cases
}
}``````

input

`````` Given Text : apple
Output     : ale
Given Text : xxyyyyx
Output     : x
Given Text : xxyyyxx
Output     :
Given Text : xyyxxyx
Output     : xyx
Given Text : xxxxyyyzyyzzxxx
Output     : z
Given Text : xyzzyxy
Output     : y
Given Text : xyxxyx
Output     :``````
``````// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ Program for
Remove all adjacent duplicate characters using recursion
*/
class RemoveCharacters
{
public:
// Recursively, removing the all adjacent similar characters
{
if (text.length() == 0)
{
return text;
}
// Define some auxiliary variable
int size = text.length() - 1;
int auxiliary = size;
string result = "";
// Execute loop until when size is less than zero
while (size >= 0)
{
while (size >= 0 && text[auxiliary] == text[size])
{
size--;
}
if (size + 1 == auxiliary)
{
// When adjacent are not same
// Then add new character at beginning of result
result = text[auxiliary] + result;
}
else
{
// This is indicate string is modified
}
// Get new index
auxiliary = size;
}
{
}
return result;
}
// Handles the request to printing calculate result
{
cout << " Given Text : " << text << endl;
cout << " Output     : " << this->removeAdjacentDuplicate(text) << endl;
}
};
int main()
{
RemoveCharacters *test = new RemoveCharacters();
// Test Cases
return 0;
}``````

input

`````` Given Text : apple
Output     : ale
Given Text : xxyyyyx
Output     : x
Given Text : xxyyyxx
Output     :
Given Text : xyyxxyx
Output     : xyx
Given Text : xxxxyyyzyyzzxxx
Output     : z
Given Text : xyzzyxy
Output     : y
Given Text : xyxxyx
Output     :``````
``````// Include namespace system
using System;
/*
Csharp Program for
Remove all adjacent duplicate characters using recursion
*/
public class RemoveCharacters
{
// Recursively, removing the all adjacent similar characters
{
if (text.Length == 0)
{
return text;
}
// Define some auxiliary variable
int size = text.Length - 1;
int auxiliary = size;
String result = "";
// Execute loop until when size is less than zero
while (size >= 0)
{
while (size >= 0 && text[auxiliary] == text[size])
{
size--;
}
if (size + 1 == auxiliary)
{
// When adjacent are not same
// Then add new character at beginning of result
result = text[auxiliary] + result;
}
else
{
// This is indicate string is modified
}
// Get new index
auxiliary = size;
}
{
}
return result;
}
// Handles the request to printing calculate result
{
Console.WriteLine(" Given Text : " + text);
Console.WriteLine(" Output     : " + this.removeAdjacentDuplicate(text));
}
public static void Main(String[] args)
{
RemoveCharacters test = new RemoveCharacters();
// Test Cases
}
}``````

input

`````` Given Text : apple
Output     : ale
Given Text : xxyyyyx
Output     : x
Given Text : xxyyyxx
Output     :
Given Text : xyyxxyx
Output     : xyx
Given Text : xxxxyyyzyyzzxxx
Output     : z
Given Text : xyzzyxy
Output     : y
Given Text : xyxxyx
Output     :``````
``````<?php
/*
Php Program for
Remove all adjacent duplicate characters using recursion
*/
class RemoveCharacters
{
// Recursively, removing the all adjacent similar characters
{
if (strlen(\$text) == 0)
{
return \$text;
}
// Define some auxiliary variable
\$size = strlen(\$text) - 1;
\$auxiliary = \$size;
\$result = "";
// Execute loop until when size is less than zero
while (\$size >= 0)
{
while (\$size >= 0 && \$text[\$auxiliary] == \$text[\$size])
{
\$size--;
}
if (\$size + 1 == \$auxiliary)
{
// When adjacent are not same
// Then add new character at beginning of result
\$result = \$text[\$auxiliary].\$result;
}
else
{
// This is indicate string is modified
}
// Get new index
\$auxiliary = \$size;
}
{
}
return \$result;
}
// Handles the request to printing calculate result
{
echo " Given Text : ".\$text.
"\n";
"\n";
}
}

function main()
{
\$test = new RemoveCharacters();
// Test Cases
}
main();``````

input

`````` Given Text : apple
Output     : ale
Given Text : xxyyyyx
Output     : x
Given Text : xxyyyxx
Output     :
Given Text : xyyxxyx
Output     : xyx
Given Text : xxxxyyyzyyzzxxx
Output     : z
Given Text : xyzzyxy
Output     : y
Given Text : xyxxyx
Output     :``````
``````/*
Node JS Program for
Remove all adjacent duplicate characters using recursion
*/
class RemoveCharacters
{
// Recursively, removing the all adjacent similar characters
{
if (text.length == 0)
{
return text;
}
// Define some auxiliary variable
var size = text.length - 1;
var auxiliary = size;
var result = "";
// Execute loop until when size is less than zero
while (size >= 0)
{
while (size >= 0 && text.charAt(auxiliary) == text.charAt(size))
{
size--;
}
if (size + 1 == auxiliary)
{
// When adjacent are not same
// Then add new character at beginning of result
result = text.charAt(auxiliary) + result;
}
else
{
// This is indicate string is modified
}
// Get new index
auxiliary = size;
}
{
}
return result;
}
// Handles the request to printing calculate result
{
console.log(" Given Text : " + text);
console.log(" Output     : " + this.removeAdjacentDuplicate(text));
}
}

function main()
{
var test = new RemoveCharacters();
// Test Cases
}
main();``````

input

`````` Given Text : apple
Output     : ale
Given Text : xxyyyyx
Output     : x
Given Text : xxyyyxx
Output     :
Given Text : xyyxxyx
Output     : xyx
Given Text : xxxxyyyzyyzzxxx
Output     : z
Given Text : xyzzyxy
Output     : y
Given Text : xyxxyx
Output     :``````
``````#  Python 3 Program for
#  Remove all adjacent duplicate characters using recursion
class RemoveCharacters :
#  Recursively, removing the all adjacent similar characters
if (len(text) == 0) :
return text

size = len(text) - 1
auxiliary = size
result = ""
#  Execute loop until when size is less than zero
while (size >= 0) :
while (size >= 0 and text[auxiliary] == text[size]) :
size -= 1

if (size + 1 == auxiliary) :
#  When adjacent are not same
#  Then add new character at beginning of result
result = text[auxiliary] + result
else :
#  This is indicate string is modified

#  Get new index
auxiliary = size

return result

#  Handles the request to printing calculate result
print(" Given Text : ", text)

def main() :
test = RemoveCharacters()
#  Test Cases

if __name__ == "__main__": main()``````

input

`````` Given Text :  apple
Output     :  ale
Given Text :  xxyyyyx
Output     :  x
Given Text :  xxyyyxx
Output     :
Given Text :  xyyxxyx
Output     :  xyx
Given Text :  xxxxyyyzyyzzxxx
Output     :  z
Given Text :  xyzzyxy
Output     :  y
Given Text :  xyxxyx
Output     :``````
``````#  Ruby Program for
#  Remove all adjacent duplicate characters using recursion
class RemoveCharacters
#  Recursively, removing the all adjacent similar characters
if (text.length == 0)
return text
end

#  Define some auxiliary variable
size = text.length - 1
auxiliary = size
result = ""
#  Execute loop until when size is less than zero
while (size >= 0)
while (size >= 0 && text[auxiliary] == text[size])
size -= 1
end

if (size + 1 == auxiliary)
#  When adjacent are not same
#  Then add new character at beginning of result
result = text[auxiliary] + result
else
#  This is indicate string is modified
end

#  Get new index
auxiliary = size
end

end

return result
end

#  Handles the request to printing calculate result
print(" Given Text : ", text, "\n")
print(" Output     : ", self.removeAdjacentDuplicate(text), "\n")
end

end

def main()
test = RemoveCharacters.new()
#  Test Cases
end

main()``````

input

`````` Given Text : apple
Output     : ale
Given Text : xxyyyyx
Output     : x
Given Text : xxyyyxx
Output     :
Given Text : xyyxxyx
Output     : xyx
Given Text : xxxxyyyzyyzzxxx
Output     : z
Given Text : xyzzyxy
Output     : y
Given Text : xyxxyx
Output     :
``````
``````/*
Scala Program for
Remove all adjacent duplicate characters using recursion
*/
class RemoveCharacters()
{
// Recursively, removing the all adjacent similar characters
def removeAdjacentDuplicate(text: String): String = {
if (text.length() == 0)
{
return text;
}
// Define some auxiliary variable
var size: Int = text.length() - 1;
var auxiliary: Int = size;
var result: String = "";
// Execute loop until when size is less than zero
while (size >= 0)
{
while (size >= 0 && text.charAt(auxiliary) == text.charAt(size))
{
size -= 1;
}
if (size + 1 == auxiliary)
{
// When adjacent are not same
// Then add new character at beginning of result
result = ""+ text.charAt(auxiliary) + result;
}
else
{
// This is indicate string is modified
}
// Get new index
auxiliary = size;
}
{
}
return result;
}
// Handles the request to printing calculate result
def removeAdjacent(text: String): Unit = {
println(" Given Text : " + text);
println(" Output     : " + removeAdjacentDuplicate(text));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var test: RemoveCharacters = new RemoveCharacters();
// Test Cases
}
}``````

input

`````` Given Text : apple
Output     : ale
Given Text : xxyyyyx
Output     : x
Given Text : xxyyyxx
Output     :
Given Text : xyyxxyx
Output     : xyx
Given Text : xxxxyyyzyyzzxxx
Output     : z
Given Text : xyzzyxy
Output     : y
Given Text : xyxxyx
Output     :``````
``````/*
Swift 4 Program for
Remove all adjacent duplicate characters using recursion
*/
class RemoveCharacters
{
// Recursively, removing the all adjacent similar characters
{
let text = Array(t);
if (text.count == 0)
{
return t;
}
// Define some auxiliary variable
var size: Int = text.count - 1;
var auxiliary: Int = size;
var result: String = "";
// Execute loop until when size is less than zero
while (size >= 0)
{
while (size >= 0 && text[auxiliary] == text[size])
{
size -= 1;
}
if (size + 1 == auxiliary)
{
// When adjacent are not same
// Then add new character at beginning of result
result = String(text[auxiliary]) + result;
}
else
{
// This is indicate string is modified
}
// Get new index
auxiliary = size;
}
{
}
return result;
}
// Handles the request to printing calculate result
{
print(" Given Text : ", text);
}
}
func main()
{
let test: RemoveCharacters = RemoveCharacters();
// Test Cases
}
main();``````

input

`````` Given Text :  apple
Output     :  ale
Given Text :  xxyyyyx
Output     :  x
Given Text :  xxyyyxx
Output     :
Given Text :  xyyxxyx
Output     :  xyx
Given Text :  xxxxyyyzyyzzxxx
Output     :  z
Given Text :  xyzzyxy
Output     :  y
Given Text :  xyxxyx
Output     :``````
``````/*
Kotlin Program for
Remove all adjacent duplicate characters using recursion
*/
class RemoveCharacters
{
// Recursively, removing the all adjacent similar characters
{
if (text.length == 0)
{
return text;
}
// Define some auxiliary variable
var size: Int = text.length - 1;
var auxiliary: Int = size;
var result: String = "";
while (size >= 0)
{
while (size >= 0 && text.get(auxiliary) == text.get(size))
{
size -= 1;
}
if (size + 1 == auxiliary)
{
// When adjacent are not same
// Then add new character at beginning of result
result = text.get(auxiliary) + result;
}
else
{
// This is indicate string is modified
}
// Get new index
auxiliary = size;
}
{
}
return result;
}
// Handles the request to printing calculate result
{
println(" Given Text : " + text);
println(" Output     : " + this.removeAdjacentDuplicate(text));
}
}
fun main(args: Array < String > ): Unit
{
val test: RemoveCharacters = RemoveCharacters();
// Test Cases
}``````

input

`````` Given Text : apple
Output     : ale
Given Text : xxyyyyx
Output     : x
Given Text : xxyyyxx
Output     :
Given Text : xyyxxyx
Output     : xyx
Given Text : xxxxyyyzyyzzxxx
Output     : z
Given Text : xyzzyxy
Output     : y
Given Text : xyxxyx
Output     :``````

Time Complexity

The time complexity of the provided algorithm depends on the length of the input `text`. The algorithm performs a linear scan through the characters of the `text` in the worst case. Therefore, the time complexity is `O(n)`, where `n` is the length of the `text`.

Resultant Output Explanation

The code correctly removes all adjacent duplicate characters using recursion for the given test cases:

1. For `text = "apple"`, the modified text is "ale".
2. For `text = "xxyyyyx"`, the modified text is "x".
3. For `text = "xxyyyxx"`, the modified text is an empty string ("").
4. For `text = "xyyxxyx"`, the modified text is "xyx".
5. For `text = "xxxxyyyzyyzzxxx"`, the modified text is "z".
6. For `text = "xyzzyxy"`, the modified text is "y".
7. For `text = "xyxxyx"`, the modified text is an empty string ("").

The algorithm efficiently removes all adjacent duplicate characters from the given text using recursion and provides the correct modified text for the provided test cases.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.