# Remove all adjacent duplicates in string using stack

The problem is to remove all adjacent duplicates in a given string using a stack. An adjacent duplicate means two identical characters next to each other in the string. The goal is to eliminate such duplicates from the original string and obtain the final string without any adjacent duplicates.

## Problem Statement

Given a string, we need to remove all adjacent duplicates from it and return the resulting string.

## Example

Consider the following examples:

1. Input: "xyxxyzyy" Output: "xz"

2. Input: "abccebbec" Output: "abc"

3. Input: "abcccb" Output: "a"

## Idea to Solve the Problem

To remove all adjacent duplicates from the string, we can use a stack to keep track of the characters as we traverse the string from left to right. We start by initializing an empty stack called `tracker`. We iterate through the string character by character. For each character, we do the following:

1. If the stack is empty, push the current character onto the stack and move to the next character.
2. If the top element of the stack is not equal to the current character, it means we have a non-adjacent character. In this case, we can push the current character onto the stack and move to the next character.
3. If the top element of the stack is equal to the current character, it means we have an adjacent duplicate. In this case, we need to skip the current character and remove the top element from the stack. We also set a `status` variable to `true` to indicate that we need to remove the top element from the stack.
4. After processing all characters, we have the non-adjacent characters left in the stack. We pop the elements from the stack one by one and collect them in reverse order to obtain the final result.

## Pseudocode

``````Function removeAdjacentDup(text):
n = length of text
Create an empty stack tracker
result = ""
status = false
i = 0

while i < n:
if tracker is empty:
Push text[i] onto tracker
i++
else if tracker.peek() != text[i]:
if status is true:
Pop the top element from tracker
Set status to false
else:
Push text[i] onto tracker
i++
else:
Set status to true
i++

if status is true and tracker is not empty:
Pop the last element from tracker

while tracker is not empty:
Append tracker.peek() to result
Pop the top element from tracker

Display "Given: " + text
Display "Result: " + result
``````

## Algorithm

1. Create a class called `Duplicates`.
2. Define a function called `removeAdjacentDup` that takes the input string `text` as a parameter.
3. Get the length of the string `n`.
4. Initialize an empty string called `result` to store the final result.
5. Create an empty stack called `tracker` to keep track of characters.
6. Initialize a boolean variable `status` to `false`.
7. Initialize a variable `i` to 0 to traverse the string.
8. While `i` is less than `n`, perform the following steps: a. If the stack `tracker` is empty, push the character `text[i]` onto the stack and increment `i`. b. If the top element of the stack `tracker` is not equal to the current character `text[i]`, do the following: i. If `status` is true, it means we need to remove the top element from the stack. Pop the top element from the stack and set `status` to `false`. ii. If `status` is false, it means we have a non-adjacent character. Push the character `text[i]` onto the stack and increment `i`. c. If the top element of the stack `tracker` is equal to the current character `text[i]`, it means we have an adjacent duplicate. Set `status` to `true` and increment `i`.
9. After processing all characters, if `status` is true and the stack `tracker` is not empty, it means we have a duplicate character at the end. Pop the last element from the stack.
10. While the stack `tracker` is not empty, do the following: a. Append the top element of the stack `tracker` to the string `result`. b. Pop the top element from the stack.
11. Display the original string and the final result.

## Code Solution

``````import java.util.Stack;
/*
Java program for
Remove all adjacent duplicates in string using stack
*/
public class Duplicates
{
{
int n = text.length();
// Create an empty tracker
Stack < Character > tracker = new Stack < Character > ();
// Auxiliary resultant variable
String result = "";
boolean status = false;
int i = 0;
// Collect all adjacent unique elements
while (i < n)
{
if (tracker.isEmpty())
{
// When tracker is empty
tracker.push(text.charAt(i));
i++;
}
else if (tracker.peek() != text.charAt(i))
{
if (status)
{
// When need to remove tracker top element
tracker.pop();
// Indicates there is no back duplicates
status = false;
}
else
{
tracker.push(text.charAt(i));
i++;
}
}
else
{
// When top of tracker element is equal to current element
status = true;
i++;
}
}
if (status == true && tracker.isEmpty() == false)
{
// Remove last duplicates
tracker.pop();
}
// This is collects resultant value
while (tracker.isEmpty() == false)
{
result = tracker.peek() + result;
tracker.pop();
}
// Display given text
System.out.print("\n Given : " + text);
// Display calculated result
System.out.print("\n Result : " + result);
}
public static void main(String[] args)
{
// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B

abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C

abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
}
}``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````
``````// Include header file
#include <iostream>
#include <stack>
#include <string>

using namespace std;
/*
C++ program for
Remove all adjacent duplicates in string using stack
*/
class Duplicates
{
{
int n = text.length();
// Create an empty tracker
stack < char > tracker;
// Auxiliary resultant variable
string result = "";
bool status = false;
int i = 0;
// Collect all adjacent unique elements
while (i < n)
{
if (tracker.empty())
{
// When tracker is empty
tracker.push(text[i]);
i++;
}
else if (tracker.top() != text[i])
{
if (status)
{
// When need to remove tracker top element
tracker.pop();
// Indicates there is no back duplicates
status = false;
}
else
{
tracker.push(text[i]);
i++;
}
}
else
{
// When top of tracker element is equal to current element
status = true;
i++;
}
}
if (status == true && tracker.empty() == false)
{
// Remove last duplicates
tracker.pop();
}
// This is collects resultant value
while (tracker.empty() == false)
{
result = (tracker.top())  +  result;
tracker.pop();
}
// Display given text
cout << "\n Given : " << text;
// Display calculated result
cout << "\n Result : " << result;
}
};
int main()
{
// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B
abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C
abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
return 0;
}``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Remove all adjacent duplicates in string using stack
*/
public class Duplicates
{
{
int n = text.Length;
// Create an empty tracker
Stack < char > tracker = new Stack < char > ();
// Auxiliary resultant variable
String result = "";
Boolean status = false;
int i = 0;
// Collect all adjacent unique elements
while (i < n)
{
if ((tracker.Count == 0))
{
// When tracker is empty
tracker.Push(text[i]);
i++;
}
else if (tracker.Peek() != text[i])
{
if (status)
{
// When need to remove tracker top element
tracker.Pop();
// Indicates there is no back duplicates
status = false;
}
else
{
tracker.Push(text[i]);
i++;
}
}
else
{
// When top of tracker element is equal to current element
status = true;
i++;
}
}
if (status == true && (tracker.Count == 0) == false)
{
// Remove last duplicates
tracker.Pop();
}
// This is collects resultant value
while ((tracker.Count == 0) == false)
{
result = tracker.Peek() + result;
tracker.Pop();
}
// Display given text
Console.Write("\n Given : " + text);
// Display calculated result
Console.Write("\n Result : " + result);
}
public static void Main(String[] args)
{
// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B
abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C
abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
}
}``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````
``````package main
import "fmt"
/*
Go program for
Remove all adjacent duplicates in string using stack
*/

var n int = len(text)
// Create an empty tracker
var tracker = make([] byte, 0)
// Auxiliary resultant variable
var result string = ""
var status bool = false
var i int = 0
// Collect all adjacent unique elements
for (i < n) {
if len(tracker) == 0 {
// When tracker is empty
tracker = append(tracker, text[i])
i++
} else if tracker[len(tracker) - 1] != text[i] {
if status {
// When need to remove tracker top element
tracker = tracker[: len(tracker) - 1]
// Indicates there is no back duplicates
status = false
} else {
tracker = append(tracker, text[i])
i++
}
} else {
// When top of tracker element is equal to current element
status = true
i++
}
}
if status == true && len(tracker) > 0 {
// Remove last duplicates
tracker = tracker[: len(tracker) - 1]
}
// This is collects resultant value
for (len(tracker) > 0 ) {
result = string(int(tracker[len(tracker) - 1])) + result
tracker = tracker[: len(tracker) - 1]
}
// Display given text
fmt.Print("\n Given : ", text)
// Display calculated result
fmt.Print("\n Result : ", result)
}
func main() {

// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B
abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C
abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
}``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````
``````<?php
/*
Php program for
Remove all adjacent duplicates in string using stack
*/
class Duplicates
{
{
\$n = strlen(\$text);
// Create an empty tracker
\$tracker = array();
// Auxiliary resultant variable
\$result = "";
\$status = false;
\$i = 0;
// Collect all adjacent unique elements
while (\$i < \$n)
{
if (empty(\$tracker))
{
// When tracker is empty
array_push(\$tracker, \$text[\$i]);
\$i++;
}
else if (end(\$tracker) != \$text[\$i])
{
if (\$status)
{
// When need to remove tracker top element
array_pop(\$tracker);
// Indicates there is no back duplicates
\$status = false;
}
else
{
array_push(\$tracker, \$text[\$i]);
\$i++;
}
}
else
{
// When top of tracker element is equal to current element
\$status = true;
\$i++;
}
}
if (\$status == true && !empty(\$tracker))
{
// Remove last duplicates
array_pop(\$tracker);
}
// This is collects resultant value
while (empty(\$tracker) == false)
{
\$result = strval(end(\$tracker)).\$result;
array_pop(\$tracker);
}
// Display given text
echo("\n Given : ".\$text);
// Display calculated result
echo("\n Result : ".\$result);
}
}

function main()
{
// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B
abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C
abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
}
main();``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````
``````/*
Node JS program for
Remove all adjacent duplicates in string using stack
*/
class Duplicates
{
{
var n = text.length;
// Create an empty tracker
var tracker = [];
// Auxiliary resultant variable
var result = "";
var status = false;
var i = 0;
// Collect all adjacent unique elements
while (i < n)
{
if ((tracker.length == 0))
{
// When tracker is empty
tracker.push(text.charAt(i));
i++;
}
else if (tracker[tracker.length - 1] !=
text.charAt(i))
{
if (status)
{
// When need to remove tracker top element
tracker.pop();
// Indicates there is no back duplicates
status = false;
}
else
{
tracker.push(text.charAt(i));
i++;
}
}
else
{
// When top of tracker element is equal to current element
status = true;
i++;
}
}
if (status == true && (tracker.length == 0) == false)
{
// Remove last duplicates
tracker.pop();
}
// This is collects resultant value
while ((tracker.length == 0) == false)
{
result = tracker[tracker.length - 1] + result;
tracker.pop();
}
// Display given text
process.stdout.write("\n Given : " + text);
// Display calculated result
process.stdout.write("\n Result : " + result);
}
}

function main()
{
// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B
abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C
abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
}
main();``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````
``````#    Python 3 program for
#    Remove all adjacent duplicates in string using stack
class Duplicates :
n = len(text)
#  Create an empty tracker
tracker = []
#  Auxiliary resultant variable
result = ""
status = False
i = 0
#  Collect all adjacent unique elements
while (i < n) :
if ((len(tracker) == 0)) :
#  When tracker is empty
tracker.append(text[i])
i += 1
elif (tracker[-1] != text[i]) :
if (status) :
#  When need to remove tracker top element
tracker.pop()
#  Indicates there is no back duplicates
status = False
else :
tracker.append(text[i])
i += 1

else :
#  When top of tracker element is equal to current element
status = True
i += 1

if (status == True and len(tracker) != 0) :
#  Remove last duplicates
tracker.pop()

#  This is collects resultant value
while ((len(tracker) == 0) == False) :
result = str(tracker[-1]) + result
tracker.pop()

#  Display given text
print("\n Given : ", text, end = "")
#  Display calculated result
print("\n Result : ", result, end = "")

def main() :
#  Test
#    Example A
#    xyxxyzyy
#    ────────
#    xyxxyzyy
#    xyyzyy
#    xzyy
#    ----------------------------------
#    xz   <-- Result
#    Example B
#    abccebbec
#    ─────────
#    abccebbec
#    abebbec
#    abeec
#    ----------------------------------
#    abc   <-- Result
#    Example C
#    abcccb
#    ─────────
#    abcccb
#    abb
#    ----------------------------------
#    a   <-- Result

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

#### Output

`````` Given :  xyxxyzyy
Result :  xz
Given :  abccebbec
Result :  abc
Given :  abcccb
Result :  a``````
``````#    Ruby program for
#    Remove all adjacent duplicates in string using stack
class Duplicates
n = text.length
#  Create an empty tracker
tracker = []
#  Auxiliary resultant variable
result = ""
status = false
i = 0
#  Collect all adjacent unique elements
while (i < n)
if ((tracker.length == 0))
#  When tracker is empty
tracker.push(text[i])
i += 1
elsif (tracker.last != text[i])
if (status)
#  When need to remove tracker top element
tracker.pop()
#  Indicates there is no back duplicates
status = false
else

tracker.push(text[i])
i += 1
end

else

#  When top of tracker element is equal to current element
status = true
i += 1
end

end

if (status == true && (tracker.length != 0))
#  Remove last duplicates
tracker.pop()
end

#  This is collects resultant value
while ((tracker.length != 0) )
result = tracker.last.to_s + result
tracker.pop()
end

#  Display given text
print("\n Given : ", text)
#  Display calculated result
print("\n Result : ", result)
end

end

def main()
#  Test
#    Example A
#    xyxxyzyy
#    ────────
#    xyxxyzyy
#    xyyzyy
#    xzyy
#    ----------------------------------
#    xz   <-- Result
#    Example B
#    abccebbec
#    ─────────
#    abccebbec
#    abebbec
#    abeec
#    ----------------------------------
#    abc   <-- Result
#    Example C
#    abcccb
#    ─────────
#    abcccb
#    abb
#    ----------------------------------
#    a   <-- Result
end

main()``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````
``````import scala.collection.mutable._;
/*
Scala program for
Remove all adjacent duplicates in string using stack
*/
class Duplicates()
{
def removeAdjacentDup(text: String): Unit = {
var n: Int = text.length();
// Create an empty tracker
var tracker: Stack[Character] = new Stack[Character]();
// Auxiliary resultant variable
var result: String = "";
var status: Boolean = false;
var i: Int = 0;
// Collect all adjacent unique elements
while (i < n)
{
if (tracker.isEmpty)
{
// When tracker is empty
tracker.push(text.charAt(i));
i += 1;
}
else if (tracker.top != text.charAt(i).toInt)
{
if (status)
{
// When need to remove tracker top element
tracker.pop;
// Indicates there is no back duplicates
status = false;
}
else
{
tracker.push(text.charAt(i));
i += 1;
}
}
else
{
// When top of tracker element is equal to current element
status = true;
i += 1;
}
}
if (status == true && tracker.isEmpty == false)
{
// Remove last duplicates
tracker.pop;
}
// This is collects resultant value
while (tracker.isEmpty == false)
{
result = tracker.top.toString() + result;
tracker.pop;
}
// Display given text
print("\n Given : " + text);
// Display calculated result
print("\n Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Duplicates = new Duplicates();
// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B
abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C
abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
}
}``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````
``````import Foundation;
/*
Swift 4 program for
Remove all adjacent duplicates in string using stack
*/
struct Stack
{
private
var items: [Character] = []
func peek()->Character
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()
{
items.removeFirst()
}
mutating func push(_ data: Character)
{
items.insert(data, at: 0)
}
}
class Duplicates
{
{
let text = Array(data);
let n: Int = text.count;
// Create an empty tracker
var tracker = Stack();
// Auxiliary resultant variable
var result: String = "";
var status: Bool = false;
var i: Int = 0;
// Collect all adjacent unique elements
while (i < n)
{
if (tracker.isEmpty())
{
// When tracker is empty
tracker.push(text[i]);
i += 1;
}
else if (!(tracker.peek() == text[i]))
{
if (status)
{
// When need to remove tracker top element
tracker.pop();
// Indicates there is no back duplicates
status = false;
}
else
{
tracker.push(text[i]);
i += 1;
}
}
else
{
// When top of tracker element is equal to current element
status = true;
i += 1;
}
}
if (status == true && tracker.isEmpty() == false)
{
// Remove last duplicates
tracker.pop();
}
// This is collects resultant value
while (tracker.isEmpty() == false)
{
result = String(tracker.peek()) + result;
tracker.pop();
}
// Display given text
print("\n Given : ", data, terminator: "");
// Display calculated result
print("\n Result : ", result, terminator: "");
}
}
func main()
{
// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B
abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C
abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
}
main();``````

#### Output

`````` Given :  xyxxyzyy
Result :  xz
Given :  abccebbec
Result :  abc
Given :  abcccb
Result :  a``````
``````import java.util.Stack;
/*
Kotlin program for
Remove all adjacent duplicates in string using stack
*/
class Duplicates
{
{
val n: Int = text.length;
// Create an empty tracker
var tracker: Stack < Char > = Stack < Char > ();
// Auxiliary resultant variable
var result: String = "";
var status: Boolean = false;
var i: Int = 0;
// Collect all adjacent unique elements
while (i < n)
{
if (tracker.empty())
{
// When tracker is empty
tracker.push(text.get(i));
i += 1;
}
else if (tracker.peek() != text.get(i))
{
if (status)
{
// When need to remove tracker top element
tracker.pop();
// Indicates there is no back duplicates
status = false;
}
else
{
tracker.push(text.get(i));
i += 1;
}
}
else
{
// When top of tracker element is equal to current element
status = true;
i += 1;
}
}
if (status == true && !tracker.empty() )
{
// Remove last duplicates
tracker.pop();
}
// This is collects resultant value
while (tracker.empty() == false)
{
result = tracker.peek().toString() + result;
tracker.pop();
}
// Display given text
print("\n Given : " + text);
// Display calculated result
print("\n Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
// Test
/*
Example A

xyxxyzyy
────────
xyxxyzyy
xyyzyy
xzyy
----------------------------------
xz   <-- Result
*/
/*
Example B
abccebbec
─────────
abccebbec
abebbec
abeec
----------------------------------
abc   <-- Result
*/
/*
Example C
abcccb
─────────
abcccb
abb
----------------------------------
a   <-- Result
*/
}``````

#### Output

`````` Given : xyxxyzyy
Result : xz
Given : abccebbec
Result : abc
Given : abcccb
Result : a``````

## Time Complexity

The time complexity of the algorithm is O(n), where n is the number of characters in the input string `text`. This is because we perform a single pass through the string and perform constant time operations of pushing and popping elements from the stack. The use of the stack does not significantly affect the overall time complexity.

## 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.