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:
-
Input: "xxzz"
- Remove first adjacent: "xxzz" -> "zz"
- Remove second adjacent: "zz" -> ""
- Result: ""
-
Input: "abccccbe"
- Remove first adjacent: "abccccbe" -> "abccbe"
- Remove second adjacent: "abccbe" -> "abbe"
- Remove third adjacent: "abbe" -> "ae"
- Result: "ae"
-
Input: "abcccbe"
- Remove first adjacent: "abcccbe" -> "abcbe"
- Result: "abcbe"
-
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
- Create a class called
AdjacentDuplicate
. - Define a function called
removeAdjacentDuplicate
which takes the input stringtext
. - Check if the length of the input string
text
is 0. If it is, return from the function. - Create an empty stack called
record
to store characters. - Create an empty string called
result
to store the final result. - Initialize a variable
element
to 0 to keep track of the current element in the string. - Iterate through the input string
text
using a while loop untilelement
is less than the length of the string: a. Check if the stackrecord
is empty or the character at the top of the stack is not equal to the character at indexelement
in the string. b. If the condition is true, push the character at indexelement
into the stackrecord
. 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. Incrementelement
by 1 to move to the next character in the string. - 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 stackrecord
and append it to the beginning of the stringresult
. b. Pop the top character from the stack. - Display "Given Text: " followed by the input string
text
. - 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;
public class AdjacentDuplicate
{
public void removeAdjacentDuplicate(String text)
{
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)
{
AdjacentDuplicate task = new AdjacentDuplicate();
// Test cases
/*
Example 1
===============
Text : xxzz
Remove first adjacent
Text : xxzz
--
After remove xx
Text : zz
Remove Second adjacent
Text : zz
--
After remove zz
Result : [] Empty String
*/
task.removeAdjacentDuplicate("xxzz");
/*
Example 2
===============
Text : abccccbe
Remove first adjacent
Text : abccccbe
--
After remove cc
Text : abccbe
Remove Second adjacent
Text : abccbe
--
After remove cc
Text : abbe
Remove Third adjacent
Text : abbe
--
After remove bb
Text : ae
Result : [ae]
*/
task.removeAdjacentDuplicate("abccccbe");
/*
Example 3
===============
Text : abcccbe
Remove first adjacent
Text : abcccbe
--
After remove cc
Text : abcbe
Result : [abcbe]
*/
task.removeAdjacentDuplicate("abcccbe");
/*
Example 4
===============
Text : xyzzz
Remove first adjacent
Text : xyzzz
--
After remove zz
Text : xyz
Result : [xyz]
*/
task.removeAdjacentDuplicate("xyzzz");
}
}
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
// 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
class AdjacentDuplicate
{
public: void removeAdjacentDuplicate(string text)
{
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()
{
AdjacentDuplicate *task = new AdjacentDuplicate();
// Test cases
/*
Example 1
===============
Text : xxzz
Remove first adjacent
Text : xxzz
--
After remove xx
Text : zz
Remove Second adjacent
Text : zz
--
After remove zz
Result : [] Empty String
*/
task->removeAdjacentDuplicate("xxzz");
/*
Example 2
===============
Text : abccccbe
Remove first adjacent
Text : abccccbe
--
After remove cc
Text : abccbe
Remove Second adjacent
Text : abccbe
--
After remove cc
Text : abbe
Remove Third adjacent
Text : abbe
--
After remove bb
Text : ae
Result : [ae]
*/
task->removeAdjacentDuplicate("abccccbe");
/*
Example 3
===============
Text : abcccbe
Remove first adjacent
Text : abcccbe
--
After remove cc
Text : abcbe
Result : [abcbe]
*/
task->removeAdjacentDuplicate("abcccbe");
/*
Example 4
===============
Text : xyzzz
Remove first adjacent
Text : xyzzz
--
After remove zz
Text : xyz
Result : [xyz]
*/
task->removeAdjacentDuplicate("xyzzz");
return 0;
}
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Remove all duplicate adjacent characters from a string using stack
public class AdjacentDuplicate
{
public void removeAdjacentDuplicate(String text)
{
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)
{
AdjacentDuplicate task = new AdjacentDuplicate();
// Test cases
/*
Example 1
===============
Text : xxzz
Remove first adjacent
Text : xxzz
--
After remove xx
Text : zz
Remove Second adjacent
Text : zz
--
After remove zz
Result : [] Empty String
*/
task.removeAdjacentDuplicate("xxzz");
/*
Example 2
===============
Text : abccccbe
Remove first adjacent
Text : abccccbe
--
After remove cc
Text : abccbe
Remove Second adjacent
Text : abccbe
--
After remove cc
Text : abbe
Remove Third adjacent
Text : abbe
--
After remove bb
Text : ae
Result : [ae]
*/
task.removeAdjacentDuplicate("abccccbe");
/*
Example 3
===============
Text : abcccbe
Remove first adjacent
Text : abcccbe
--
After remove cc
Text : abcbe
Result : [abcbe]
*/
task.removeAdjacentDuplicate("abcccbe");
/*
Example 4
===============
Text : xyzzz
Remove first adjacent
Text : xyzzz
--
After remove zz
Text : xyz
Result : [xyz]
*/
task.removeAdjacentDuplicate("xyzzz");
}
}
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
<?php
// Php program for
// Remove all duplicate adjacent characters from a string using stack
class AdjacentDuplicate
{
public function removeAdjacentDuplicate($text)
{
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()
{
$task = new AdjacentDuplicate();
// Test cases
/*
Example 1
===============
Text : xxzz
Remove first adjacent
Text : xxzz
--
After remove xx
Text : zz
Remove Second adjacent
Text : zz
--
After remove zz
Result : [] Empty String
*/
$task->removeAdjacentDuplicate("xxzz");
/*
Example 2
===============
Text : abccccbe
Remove first adjacent
Text : abccccbe
--
After remove cc
Text : abccbe
Remove Second adjacent
Text : abccbe
--
After remove cc
Text : abbe
Remove Third adjacent
Text : abbe
--
After remove bb
Text : ae
Result : [ae]
*/
$task->removeAdjacentDuplicate("abccccbe");
/*
Example 3
===============
Text : abcccbe
Remove first adjacent
Text : abcccbe
--
After remove cc
Text : abcbe
Result : [abcbe]
*/
$task->removeAdjacentDuplicate("abcccbe");
/*
Example 4
===============
Text : xyzzz
Remove first adjacent
Text : xyzzz
--
After remove zz
Text : xyz
Result : [xyz]
*/
$task->removeAdjacentDuplicate("xyzzz");
}
main();
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
// Node JS program for
// Remove all duplicate adjacent characters from a string using stack
class AdjacentDuplicate
{
removeAdjacentDuplicate(text)
{
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()
{
var task = new AdjacentDuplicate();
// Test cases
/*
Example 1
===============
Text : xxzz
Remove first adjacent
Text : xxzz
--
After remove xx
Text : zz
Remove Second adjacent
Text : zz
--
After remove zz
Result : [] Empty String
*/
task.removeAdjacentDuplicate("xxzz");
/*
Example 2
===============
Text : abccccbe
Remove first adjacent
Text : abccccbe
--
After remove cc
Text : abccbe
Remove Second adjacent
Text : abccbe
--
After remove cc
Text : abbe
Remove Third adjacent
Text : abbe
--
After remove bb
Text : ae
Result : [ae]
*/
task.removeAdjacentDuplicate("abccccbe");
/*
Example 3
===============
Text : abcccbe
Remove first adjacent
Text : abcccbe
--
After remove cc
Text : abcbe
Result : [abcbe]
*/
task.removeAdjacentDuplicate("abcccbe");
/*
Example 4
===============
Text : xyzzz
Remove first adjacent
Text : xyzzz
--
After remove zz
Text : xyz
Result : [xyz]
*/
task.removeAdjacentDuplicate("xyzzz");
}
main();
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
from queue import LifoQueue
# Python 3 program for
# Remove all duplicate adjacent characters from a string using stack
class AdjacentDuplicate :
def removeAdjacentDuplicate(self, text) :
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() :
task = AdjacentDuplicate()
# Test cases
# Example 1
# ===============
# Text : xxzz
# Remove first adjacent
# Text : xxzz
# --
# After remove xx
# Text : zz
# Remove Second adjacent
# Text : zz
# --
# After remove zz
# Result : [] Empty String
task.removeAdjacentDuplicate("xxzz")
# Example 2
# ===============
# Text : abccccbe
# Remove first adjacent
# Text : abccccbe
# --
# After remove cc
# Text : abccbe
# Remove Second adjacent
# Text : abccbe
# --
# After remove cc
# Text : abbe
# Remove Third adjacent
# Text : abbe
# --
# After remove bb
# Text : ae
# Result : [ae]
task.removeAdjacentDuplicate("abccccbe")
# Example 3
# ===============
# Text : abcccbe
# Remove first adjacent
# Text : abcccbe
# --
# After remove cc
# Text : abcbe
# Result : [abcbe]
task.removeAdjacentDuplicate("abcccbe")
# Example 4
# ===============
# Text : xyzzz
# Remove first adjacent
# Text : xyzzz
# --
# After remove zz
# Text : xyz
# Result : [xyz]
task.removeAdjacentDuplicate("xyzzz")
if __name__ == "__main__": main()
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
# Ruby program for
# Remove all duplicate adjacent characters from a string using stack
class AdjacentDuplicate
def removeAdjacentDuplicate(text)
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()
task = AdjacentDuplicate.new()
# Test cases
# Example 1
# ===============
# Text : xxzz
# Remove first adjacent
# Text : xxzz
# --
# After remove xx
# Text : zz
# Remove Second adjacent
# Text : zz
# --
# After remove zz
# Result : [] Empty String
task.removeAdjacentDuplicate("xxzz")
# Example 2
# ===============
# Text : abccccbe
# Remove first adjacent
# Text : abccccbe
# --
# After remove cc
# Text : abccbe
# Remove Second adjacent
# Text : abccbe
# --
# After remove cc
# Text : abbe
# Remove Third adjacent
# Text : abbe
# --
# After remove bb
# Text : ae
# Result : [ae]
task.removeAdjacentDuplicate("abccccbe")
# Example 3
# ===============
# Text : abcccbe
# Remove first adjacent
# Text : abcccbe
# --
# After remove cc
# Text : abcbe
# Result : [abcbe]
task.removeAdjacentDuplicate("abcccbe")
# Example 4
# ===============
# Text : xyzzz
# Remove first adjacent
# Text : xyzzz
# --
# After remove zz
# Text : xyz
# Result : [xyz]
task.removeAdjacentDuplicate("xyzzz")
end
main()
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
import scala.collection.mutable._;
// Scala program for
// Remove all duplicate adjacent characters from a string using stack
class AdjacentDuplicate()
{
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 = {
var task: AdjacentDuplicate = new AdjacentDuplicate();
// Test cases
/*
Example 1
===============
Text : xxzz
Remove first adjacent
Text : xxzz
--
After remove xx
Text : zz
Remove Second adjacent
Text : zz
--
After remove zz
Result : [] Empty String
*/
task.removeAdjacentDuplicate("xxzz");
/*
Example 2
===============
Text : abccccbe
Remove first adjacent
Text : abccccbe
--
After remove cc
Text : abccbe
Remove Second adjacent
Text : abccbe
--
After remove cc
Text : abbe
Remove Third adjacent
Text : abbe
--
After remove bb
Text : ae
Result : [ae]
*/
task.removeAdjacentDuplicate("abccccbe");
/*
Example 3
===============
Text : abcccbe
Remove first adjacent
Text : abcccbe
--
After remove cc
Text : abcbe
Result : [abcbe]
*/
task.removeAdjacentDuplicate("abcccbe");
/*
Example 4
===============
Text : xyzzz
Remove first adjacent
Text : xyzzz
--
After remove zz
Text : xyz
Result : [xyz]
*/
task.removeAdjacentDuplicate("xyzzz");
}
}
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
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)
}
}
class AdjacentDuplicate
{
func removeAdjacentDuplicate(_ data: String)
{
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()
{
let task: AdjacentDuplicate = AdjacentDuplicate();
// Test cases
/*
Example 1
===============
Text : xxzz
Remove first adjacent
Text : xxzz
--
After remove xx
Text : zz
Remove Second adjacent
Text : zz
--
After remove zz
Result : [] Empty String
*/
task.removeAdjacentDuplicate("xxzz");
/*
Example 2
===============
Text : abccccbe
Remove first adjacent
Text : abccccbe
--
After remove cc
Text : abccbe
Remove Second adjacent
Text : abccbe
--
After remove cc
Text : abbe
Remove Third adjacent
Text : abbe
--
After remove bb
Text : ae
Result : [ae]
*/
task.removeAdjacentDuplicate("abccccbe");
/*
Example 3
===============
Text : abcccbe
Remove first adjacent
Text : abcccbe
--
After remove cc
Text : abcbe
Result : [abcbe]
*/
task.removeAdjacentDuplicate("abcccbe");
/*
Example 4
===============
Text : xyzzz
Remove first adjacent
Text : xyzzz
--
After remove zz
Text : xyz
Result : [xyz]
*/
task.removeAdjacentDuplicate("xyzzz");
}
main();
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
import java.util.Stack;
// Kotlin program for
// Remove all duplicate adjacent characters from a string using stack
class AdjacentDuplicate
{
fun 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
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
{
val task: AdjacentDuplicate = AdjacentDuplicate();
// Test cases
/*
Example 1
===============
Text : xxzz
Remove first adjacent
Text : xxzz
--
After remove xx
Text : zz
Remove Second adjacent
Text : zz
--
After remove zz
Result : [] Empty String
*/
task.removeAdjacentDuplicate("xxzz");
/*
Example 2
===============
Text : abccccbe
Remove first adjacent
Text : abccccbe
--
After remove cc
Text : abccbe
Remove Second adjacent
Text : abccbe
--
After remove cc
Text : abbe
Remove Third adjacent
Text : abbe
--
After remove bb
Text : ae
Result : [ae]
*/
task.removeAdjacentDuplicate("abccccbe");
/*
Example 3
===============
Text : abcccbe
Remove first adjacent
Text : abcccbe
--
After remove cc
Text : abcbe
Result : [abcbe]
*/
task.removeAdjacentDuplicate("abcccbe");
/*
Example 4
===============
Text : xyzzz
Remove first adjacent
Text : xyzzz
--
After remove zz
Text : xyz
Result : [xyz]
*/
task.removeAdjacentDuplicate("xyzzz");
}
input
Given Text : xxzz
Remove Adjacent Duplicate : []
Given Text : abccccbe
Remove Adjacent Duplicate : [ae]
Given Text : abcccbe
Remove Adjacent Duplicate : [abcbe]
Given Text : xyzzz
Remove Adjacent Duplicate : [xyz]
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).
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.
New Comment