Posted on by Kalkicode
Code Stack

# Remove all duplicate adjacent characters from a string using stack

The problem is to remove all duplicate adjacent characters from a given string using a stack. We are given a string, and we need to process it to remove all adjacent characters that are the same. If two identical characters occur next to each other, they should be removed. The process continues until no more adjacent duplicates are left in the string.

## Example

Consider the following examples:

1. Input: "xxzz"

• Remove first adjacent: "xxzz" -> "zz"
• Remove second adjacent: "zz" -> ""
• Result: ""
2. Input: "abccccbe"

• Remove first adjacent: "abccccbe" -> "abccbe"
• Remove second adjacent: "abccbe" -> "abbe"
• Remove third adjacent: "abbe" -> "ae"
• Result: "ae"
3. Input: "abcccbe"

• Remove first adjacent: "abcccbe" -> "abcbe"
• Result: "abcbe"
4. Input: "xyzzz"

• Remove first adjacent: "xyzzz" -> "xyz"
• Result: "xyz"

## Idea to Solve the Problem

To remove all duplicate adjacent characters from the string, we can use a stack to keep track of the characters. We iterate through the string from left to right. For each character, if the stack is empty or the current character is different from the character at the top of the stack, we push the current character into the stack. Otherwise, if the current character is the same as the character at the top of the stack, we pop the character from the stack to remove the adjacent duplicate.

## Pseudocode

``````Function removeAdjacentDuplicate(text):
If text is empty:
Return
Create an empty stack called record
Create an empty string called result
Set element to 0
While element is less than the length of text:
If record is empty or record.peek() is not equal to text[element]:
Push text[element] into record
Else:
Pop from record
Increment element by 1
While record is not empty:
Append record.peek() to the beginning of result
Pop from record
Display "Given Text: " + text
Display "Remove Adjacent Duplicate: [" + result + "]"
``````

## Algorithm

1. Create a class called `AdjacentDuplicate`.
2. Define a function called `removeAdjacentDuplicate` which takes the input string `text`.
3. Check if the length of the input string `text` is 0. If it is, return from the function.
4. Create an empty stack called `record` to store characters.
5. Create an empty string called `result` to store the final result.
6. Initialize a variable `element` to 0 to keep track of the current element in the string.
7. Iterate through the input string `text` using a while loop until `element` is less than the length of the string: a. Check if the stack `record` is empty or the character at the top of the stack is not equal to the character at index `element` in the string. b. If the condition is true, push the character at index `element` into the stack `record`. c. If the condition is false, it means the current character is the same as the character at the top of the stack, so pop the character from the stack to remove the adjacent duplicate. d. Increment `element` by 1 to move to the next character in the string.
8. After the loop, the stack `record` will contain the non-adjacent duplicate characters in reverse order. So, iterate through the stack using another while loop until it becomes empty: a. Get the top character from the stack `record` and append it to the beginning of the string `result`. b. Pop the top character from the stack.
9. Display "Given Text: " followed by the input string `text`.
10. Display "Remove Adjacent Duplicate: [" followed by the string `result` followed by "]" to show the final result.

## Code Solution

``````// Java program for
// Remove all duplicate adjacent characters from a string using stack
import java.util.Stack;
{
{
if (text.length() == 0)
{
return;
}
// Define use useful resultant variables
String result = "";
int element = 0;
// Use to collect string characters
Stack < Character > record = new Stack < Character > ();
// Find all unique adjacent characters
while (element < text.length())
{
if (record.isEmpty() || record.peek() != text.charAt(element))
{
// When stack is empty or
// Two adjacent characters are not same
record.push(text.charAt(element));
}
else
{
// Two adjacent characters are same
// Remove stack element
record.pop();
}
// visit to next character
element++;
}
// Collect non adjacent duplicate characters
while (!record.isEmpty())
{
result = record.peek() + result;
record.pop();
}
// Display given text
System.out.println(" Given Text : " + text);
// Display calculated result
System.out.println(" Remove Adjacent Duplicate : [" + result + "]");
}
public static void main(String[] args)
{
// Test cases
/*
Example 1
===============
Text : xxzz

Text : xxzz
--
After remove xx
Text : zz

Text : zz
--
After remove zz
Result : [] Empty String

*/
/*
Example 2
===============
Text : abccccbe

Text : abccccbe
--
After remove cc
Text : abccbe

Text : abccbe
--
After remove cc
Text : abbe

Text : abbe
--
After remove bb
Text : ae

Result : [ae]
*/
/*
Example 3
===============
Text : abcccbe

Text : abcccbe
--
After remove cc
Text : abcbe

Result : [abcbe]
*/
/*
Example 4
===============
Text : xyzzz

Text : xyzzz
--
After remove zz
Text : xyz

Result : [xyz]
*/
}
}``````

#### input

`````` Given Text : xxzz
Given Text : abccccbe
Given Text : abcccbe
Given Text : xyzzz
``````// Include header file
#include <iostream>
#include <stack>
#include <string>

using namespace std;
// C++ program for
// Remove all duplicate adjacent characters from a string using stack
{
{
if (text.length() == 0)
{
return;
}
// Define use useful resultant variables
string result = "";
int element = 0;
// Use to collect string characters
stack < char > record ;
// Find all unique adjacent characters
while (element < text.length())
{
if (record.empty() || record.top() != text[element])
{
// When stack is empty or
// Two adjacent characters are not same
record.push(text[element]);
}
else
{
// Two adjacent characters are same
// Remove stack element
record.pop();
}
// visit to next character
element++;
}
// Collect non adjacent duplicate characters
while (!record.empty())
{
result = record.top() +  result;
record.pop();
}
// Display given text
cout << " Given Text : " << text << endl;
// Display calculated result
cout << " Remove Adjacent Duplicate : [" << result << "]" << endl;
}
};
int main()
{
// Test cases
/*
Example 1
===============
Text : xxzz
Text : xxzz
--
After remove xx
Text : zz

Text : zz
--
After remove zz
Result : [] Empty String
*/
/*
Example 2
===============
Text : abccccbe
Text : abccccbe
--
After remove cc
Text : abccbe

Text : abccbe
--
After remove cc
Text : abbe
Text : abbe
--
After remove bb
Text : ae

Result : [ae]
*/
/*
Example 3
===============
Text : abcccbe
Text : abcccbe
--
After remove cc
Text : abcbe

Result : [abcbe]
*/
/*
Example 4
===============
Text : xyzzz
Text : xyzzz
--
After remove zz
Text : xyz

Result : [xyz]
*/
return 0;
}``````

#### input

`````` Given Text : xxzz
Given Text : abccccbe
Given Text : abcccbe
Given Text : xyzzz
``````// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Remove all duplicate adjacent characters from a string using stack
{
{
if (text.Length == 0)
{
return;
}
// Define use useful resultant variables
String result = "";
int element = 0;
// Use to collect string characters
Stack < char > record = new Stack < char > ();
// Find all unique adjacent characters
while (element < text.Length)
{
if ((record.Count == 0) || record.Peek() != text[element])
{
// When stack is empty or
// Two adjacent characters are not same
record.Push(text[element]);
}
else
{
// Two adjacent characters are same
// Remove stack element
record.Pop();
}
// visit to next character
element++;
}
// Collect non adjacent duplicate characters
while (!(record.Count == 0))
{
result = record.Peek() + result;
record.Pop();
}
// Display given text
Console.WriteLine(" Given Text : " + text);
// Display calculated result
Console.WriteLine(" Remove Adjacent Duplicate : [" + result + "]");
}
public static void Main(String[] args)
{
// Test cases
/*
Example 1
===============
Text : xxzz
Text : xxzz
--
After remove xx
Text : zz

Text : zz
--
After remove zz
Result : [] Empty String
*/
/*
Example 2
===============
Text : abccccbe
Text : abccccbe
--
After remove cc
Text : abccbe

Text : abccbe
--
After remove cc
Text : abbe
Text : abbe
--
After remove bb
Text : ae

Result : [ae]
*/
/*
Example 3
===============
Text : abcccbe
Text : abcccbe
--
After remove cc
Text : abcbe

Result : [abcbe]
*/
/*
Example 4
===============
Text : xyzzz
Text : xyzzz
--
After remove zz
Text : xyz

Result : [xyz]
*/
}
}``````

#### input

`````` Given Text : xxzz
Given Text : abccccbe
Given Text : abcccbe
Given Text : xyzzz
``````<?php
// Php program for
// Remove all duplicate adjacent characters from a string using stack
{
{
if (strlen(\$text) == 0)
{
return;
}
// Define use useful resultant variables
\$result = "";
\$element = 0;
// Use to collect string characters
\$record =  array();
// Find all unique adjacent characters
while (\$element < strlen(\$text))
{
if (empty(\$record) || \$record[0] != \$text[\$element])
{
// When stack is empty or
// Two adjacent characters are not same
array_unshift(\$record, \$text[\$element]);
}
else
{
// Two adjacent characters are same
// Remove stack element
array_shift(\$record);
}
// visit to next character
\$element++;
}
// Collect non adjacent duplicate characters
while (!empty(\$record))
{
\$result = strval(\$record[0]).\$result;
array_shift(\$record);
}
// Display given text
echo("\n Given Text : ".\$text);
// Display calculated result
echo("\n Remove Adjacent Duplicate : [".\$result."]");
}
}

function main()
{
// Test cases
/*
Example 1
===============
Text : xxzz
Text : xxzz
--
After remove xx
Text : zz

Text : zz
--
After remove zz
Result : [] Empty String
*/
/*
Example 2
===============
Text : abccccbe
Text : abccccbe
--
After remove cc
Text : abccbe

Text : abccbe
--
After remove cc
Text : abbe
Text : abbe
--
After remove bb
Text : ae

Result : [ae]
*/
/*
Example 3
===============
Text : abcccbe
Text : abcccbe
--
After remove cc
Text : abcbe

Result : [abcbe]
*/
/*
Example 4
===============
Text : xyzzz
Text : xyzzz
--
After remove zz
Text : xyz

Result : [xyz]
*/
}
main();``````

#### input

`````` Given Text : xxzz
Given Text : abccccbe
Given Text : abcccbe
Given Text : xyzzz
``````// Node JS program for
// Remove all duplicate adjacent characters from a string using stack
{
{
if (text.length == 0)
{
return;
}
// Define use useful resultant variables
var result = "";
var element = 0;
// Use to collect string characters
var record = [];
// Find all unique adjacent characters
while (element < text.length)
{
if ((record.length == 0) ||
record[record.length - 1] != text.charAt(element))
{
// When stack is empty or
// Two adjacent characters are not same
record.push(text.charAt(element));
}
else
{
// Two adjacent characters are same
// Remove stack element
record.pop();
}
// visit to next character
element++;
}
// Collect non adjacent duplicate characters
while (!(record.length == 0))
{
result = record[record.length - 1] + result;
record.pop();
}
// Display given text
console.log(" Given Text : " + text);
// Display calculated result
console.log(" Remove Adjacent Duplicate : [" + result + "]");
}
}

function main()
{
// Test cases
/*
Example 1
===============
Text : xxzz
Text : xxzz
--
After remove xx
Text : zz

Text : zz
--
After remove zz
Result : [] Empty String
*/
/*
Example 2
===============
Text : abccccbe
Text : abccccbe
--
After remove cc
Text : abccbe

Text : abccbe
--
After remove cc
Text : abbe
Text : abbe
--
After remove bb
Text : ae

Result : [ae]
*/
/*
Example 3
===============
Text : abcccbe
Text : abcccbe
--
After remove cc
Text : abcbe

Result : [abcbe]
*/
/*
Example 4
===============
Text : xyzzz
Text : xyzzz
--
After remove zz
Text : xyz

Result : [xyz]
*/
}
main();``````

#### input

`````` Given Text : xxzz
Given Text : abccccbe
Given Text : abcccbe
Given Text : xyzzz
``````from queue import LifoQueue
#  Python 3 program for
#  Remove all duplicate adjacent characters from a string using stack

if (len(text) == 0) :
return

#  Define use useful resultant variables
result = ""
element = 0
#  Use to collect string characters
record = []
#  Find all unique adjacent characters
while (element < len(text)) :
if (len(record) == 0 or record[-1] != text[element]) :
#  When stack is empty or
#  Two adjacent characters are not same
record.append(text[element])
else :
#  Two adjacent characters are same
#  Remove element
record.pop()

#  visit to next character
element += 1

#  Collect non adjacent duplicate characters
while (len(record) != 0) :
result = record.pop() + result

#  Display given text
print(" Given Text : ", text)
#  Display calculated result
print(" Remove Adjacent Duplicate : [{0}]".format(result))

def main() :
#  Test cases
#    Example 1
#    ===============
#    Text : xxzz
#    Text : xxzz
#           --
#    After remove xx
#    Text : zz
#    Text : zz
#           --
#    After remove zz
#    Result : [] Empty String
#    Example 2
#    ===============
#    Text : abccccbe
#    Text : abccccbe
#             --
#    After remove cc
#    Text : abccbe
#    Text : abccbe
#             --
#    After remove cc
#    Text : abbe
#    Text : abbe
#            --
#    After remove bb
#    Text : ae
#    Result : [ae]
#    Example 3
#    ===============
#    Text : abcccbe
#    Text : abcccbe
#             --
#    After remove cc
#    Text : abcbe
#    Result : [abcbe]
#    Example 4
#    ===============
#    Text : xyzzz
#    Text : xyzzz
#             --
#    After remove zz
#    Text : xyz
#    Result : [xyz]

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

#### input

`````` Given Text :  xxzz
Given Text :  abccccbe
Given Text :  abcccbe
Given Text :  xyzzz
``````#  Ruby program for
#  Remove all duplicate adjacent characters from a string using stack
if (text.length == 0)
return
end

#  Define use useful resultant variables
result = ""
element = 0
#  Use to collect string characters
record = []
#  Find all unique adjacent characters
while (element < text.length)
if ((record.length == 0) || record.last != text[element])
#  When stack is empty or
#  Two adjacent characters are not same
record.push(text[element])
else
#  Two adjacent characters are same
#  Remove stack element
record.pop()
end

#  visit to next character
element += 1
end

#  Collect non adjacent duplicate characters
while (!(record.length == 0))
result = record.last.to_s + result
record.pop()
end

#  Display given text
print(" Given Text : ", text, "\n")
#  Display calculated result
print(" Remove Adjacent Duplicate : [", result ,"]", "\n")
end

end

def main()
#  Test cases
#    Example 1
#    ===============
#    Text : xxzz
#    Text : xxzz
#           --
#    After remove xx
#    Text : zz
#    Text : zz
#           --
#    After remove zz
#    Result : [] Empty String
#    Example 2
#    ===============
#    Text : abccccbe
#    Text : abccccbe
#             --
#    After remove cc
#    Text : abccbe
#    Text : abccbe
#             --
#    After remove cc
#    Text : abbe
#    Text : abbe
#            --
#    After remove bb
#    Text : ae
#    Result : [ae]
#    Example 3
#    ===============
#    Text : abcccbe
#    Text : abcccbe
#             --
#    After remove cc
#    Text : abcbe
#    Result : [abcbe]
#    Example 4
#    ===============
#    Text : xyzzz
#    Text : xyzzz
#             --
#    After remove zz
#    Text : xyz
#    Result : [xyz]
end

main()``````

#### input

`````` Given Text : xxzz
Given Text : abccccbe
Given Text : abcccbe
Given Text : xyzzz
``````
``````import scala.collection.mutable._;
// Scala program for
// Remove all duplicate adjacent characters from a string using stack
{
def removeAdjacentDuplicate(text: String): Unit = {
if (text.length() == 0)
{
return;
}
// Define use useful resultant variables
var result: String = "";
var element: Int = 0;
// Use to collect string characters
var record: Stack[Character] = new Stack[Character]();
// Find all unique adjacent characters
while (element < text.length())
{
if (record.isEmpty || record.top != text.charAt(element).toInt)
{
// When stack is empty or
// Two adjacent characters are not same
record.push(text.charAt(element));
}
else
{
// Two adjacent characters are same
// Remove stack element
record.pop;
}
// visit to next character
element += 1;
}
// Collect non adjacent duplicate characters
while (!record.isEmpty)
{
result = record.top.toString() + result;
record.pop;
}
// Display given text
println(" Given Text : " + text);
// Display calculated result
println(" Remove Adjacent Duplicate : [" + result + "]");
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Test cases
/*
Example 1
===============
Text : xxzz
Text : xxzz
--
After remove xx
Text : zz

Text : zz
--
After remove zz
Result : [] Empty String
*/
/*
Example 2
===============
Text : abccccbe
Text : abccccbe
--
After remove cc
Text : abccbe

Text : abccbe
--
After remove cc
Text : abbe
Text : abbe
--
After remove bb
Text : ae

Result : [ae]
*/
/*
Example 3
===============
Text : abcccbe
Text : abcccbe
--
After remove cc
Text : abcbe

Result : [abcbe]
*/
/*
Example 4
===============
Text : xyzzz
Text : xyzzz
--
After remove zz
Text : xyz

Result : [xyz]
*/
}
}``````

#### input

`````` Given Text : xxzz
Given Text : abccccbe
Given Text : abcccbe
Given Text : xyzzz
``````import Foundation
// Swift 4 program for
// Remove all duplicate adjacent characters from a string using stack
// implement 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)
}
}
{
{
let text = Array(data);
if (text.count == 0)
{
return;
}

// Define use useful resultant variables
var result: String = "";
var element: Int = 0;
// Use to collect string characters
var record = Stack();
// Find all unique adjacent characters
while (element < text.count)
{
if (record.isEmpty() || !(record.peek() == text[element]))
{
// When stack is empty or
// Two adjacent characters are not same
record.push(text[element]);
}
else
{
// Two adjacent characters are same
// Remove stack element
record.pop();
}
// visit to next character
element += 1;
}
// Collect non adjacent duplicate characters
while (!record.isEmpty())
{
result = String(record.peek()) + result;
record.pop();
}
// Display given text
print(" Given Text : ", data);
// Display calculated result
print(" Remove Adjacent Duplicate : [\(result)]");
}
}
func main()
{
// Test cases
/*
Example 1
===============
Text : xxzz
Text : xxzz
--
After remove xx
Text : zz

Text : zz
--
After remove zz
Result : [] Empty String
*/
/*
Example 2
===============
Text : abccccbe
Text : abccccbe
--
After remove cc
Text : abccbe

Text : abccbe
--
After remove cc
Text : abbe
Text : abbe
--
After remove bb
Text : ae

Result : [ae]
*/
/*
Example 3
===============
Text : abcccbe
Text : abcccbe
--
After remove cc
Text : abcbe

Result : [abcbe]
*/
/*
Example 4
===============
Text : xyzzz
Text : xyzzz
--
After remove zz
Text : xyz

Result : [xyz]
*/
}
main();``````

#### input

`````` Given Text :  xxzz
Given Text :  abccccbe
Given Text :  abcccbe
Given Text :  xyzzz
``````import java.util.Stack;
// Kotlin program for
// Remove all duplicate adjacent characters from a string using stack
{
{
if (text.length == 0)
{
return;
}
// Define use useful resultant variables
var result: String = "";
var element: Int = 0;
// Use to collect string characters
val record = Stack<Char>();
// Find all unique adjacent characters
while (element < text.length)
{
if (record.empty() || record.peek() != text.get(element))
{
// When stack is empty or
// Two adjacent characters are not same
record.push(text.get(element));
}
else
{
// Two adjacent characters are same
// Remove stack element
record.pop();
}
// visit to next character
element += 1;
}
// Collect non adjacent duplicate characters
while (!record.empty())
{
result = record.peek().toString() + result;
record.pop();
}
// Display given text
println(" Given Text : " + text);
// Display calculated result
println(" Remove Adjacent Duplicate : [" + result + "]");
}
}
fun main(args: Array < String > ): Unit
{
// Test cases
/*
Example 1
===============
Text : xxzz
Text : xxzz
--
After remove xx
Text : zz

Text : zz
--
After remove zz
Result : [] Empty String
*/
/*
Example 2
===============
Text : abccccbe
Text : abccccbe
--
After remove cc
Text : abccbe

Text : abccbe
--
After remove cc
Text : abbe
Text : abbe
--
After remove bb
Text : ae

Result : [ae]
*/
/*
Example 3
===============
Text : abcccbe
Text : abcccbe
--
After remove cc
Text : abcbe

Result : [abcbe]
*/
/*
Example 4
===============
Text : xyzzz
Text : xyzzz
--
After remove zz
Text : xyz

Result : [xyz]
*/
}``````

#### input

`````` Given Text : xxzz
Given Text : abccccbe
Given Text : abcccbe
Given Text : xyzzz

## Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the input string. We iterate through the string once to remove the adjacent duplicates, and then we iterate through the stack once to construct the resultant string. Both operations take linear time, so the overall time complexity is O(n).

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

Categories
Relative Post