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:
-
Input: "xyxxyzyy" Output: "xz"
-
Input: "abccebbec" Output: "abc"
-
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:
- If the stack is empty, push the current character onto the stack and move to the next character.
- 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.
- 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 totrue
to indicate that we need to remove the top element from the stack. - 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
- Create a class called
Duplicates
. - Define a function called
removeAdjacentDup
that takes the input stringtext
as a parameter. - Get the length of the string
n
. - Initialize an empty string called
result
to store the final result. - Create an empty stack called
tracker
to keep track of characters. - Initialize a boolean variable
status
tofalse
. - Initialize a variable
i
to 0 to traverse the string. - While
i
is less thann
, perform the following steps: a. If the stacktracker
is empty, push the charactertext[i]
onto the stack and incrementi
. b. If the top element of the stacktracker
is not equal to the current charactertext[i]
, do the following: i. Ifstatus
is true, it means we need to remove the top element from the stack. Pop the top element from the stack and setstatus
tofalse
. ii. Ifstatus
is false, it means we have a non-adjacent character. Push the charactertext[i]
onto the stack and incrementi
. c. If the top element of the stacktracker
is equal to the current charactertext[i]
, it means we have an adjacent duplicate. Setstatus
totrue
and incrementi
. - After processing all characters, if
status
is true and the stacktracker
is not empty, it means we have a duplicate character at the end. Pop the last element from the stack. - While the stack
tracker
is not empty, do the following: a. Append the top element of the stacktracker
to the stringresult
. b. Pop the top element from the stack. - 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
{
public void removeAdjacentDup(String text)
{
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
{
// Add unique adjacent
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)
{
Duplicates task = new Duplicates();
// Test
/*
Example A
xyxxyzyy
────────
xyxxyzyy
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
task.removeAdjacentDup("xyxxyzyy");
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
task.removeAdjacentDup("abccebbec");
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
task.removeAdjacentDup("abcccb");
}
}
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
{
public: void removeAdjacentDup(string text)
{
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
{
// Add unique adjacent
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()
{
Duplicates *task = new Duplicates();
// Test
/*
Example A
xyxxyzyy
────────
xyxxyzyy
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
task->removeAdjacentDup("xyxxyzyy");
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
task->removeAdjacentDup("abccebbec");
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
task->removeAdjacentDup("abcccb");
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
{
public void removeAdjacentDup(String text)
{
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
{
// Add unique adjacent
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)
{
Duplicates task = new Duplicates();
// Test
/*
Example A
xyxxyzyy
────────
xyxxyzyy
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
task.removeAdjacentDup("xyxxyzyy");
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
task.removeAdjacentDup("abccebbec");
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
task.removeAdjacentDup("abcccb");
}
}
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
*/
func removeAdjacentDup(text string) {
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 {
// Add unique adjacent
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
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
removeAdjacentDup("xyxxyzyy")
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
removeAdjacentDup("abccebbec")
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
removeAdjacentDup("abcccb")
}
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
{
public function removeAdjacentDup($text)
{
$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
{
// Add unique adjacent
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()
{
$task = new Duplicates();
// Test
/*
Example A
xyxxyzyy
────────
xyxxyzyy
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
$task->removeAdjacentDup("xyxxyzyy");
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
$task->removeAdjacentDup("abccebbec");
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
$task->removeAdjacentDup("abcccb");
}
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
{
removeAdjacentDup(text)
{
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
{
// Add unique adjacent
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()
{
var task = new Duplicates();
// Test
/*
Example A
xyxxyzyy
────────
xyxxyzyy
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
task.removeAdjacentDup("xyxxyzyy");
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
task.removeAdjacentDup("abccebbec");
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
task.removeAdjacentDup("abcccb");
}
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 :
def removeAdjacentDup(self, text) :
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 :
# Add unique adjacent
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() :
task = Duplicates()
# Test
# Example A
# xyxxyzyy
# ────────
# xyxxyzyy
# -- ->remove adjacent xx
# xyyzyy
# -- ->remove adjacent yy
# xzyy
# -- ->remove adjacent yy
# ----------------------------------
# xz <-- Result
task.removeAdjacentDup("xyxxyzyy")
# Example B
# abccebbec
# ─────────
# abccebbec
# -- ->remove adjacent cc
# abebbec
# -- ->remove adjacent bb
# abeec
# -- ->remove adjacent ee
# ----------------------------------
# abc <-- Result
task.removeAdjacentDup("abccebbec")
# Example C
# abcccb
# ─────────
# abcccb
# --- ->remove adjacent ccc
# abb
# -- ->remove adjacent bb
# ----------------------------------
# a <-- Result
task.removeAdjacentDup("abcccb")
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
def removeAdjacentDup(text)
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
# Add unique adjacent
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()
task = Duplicates.new()
# Test
# Example A
# xyxxyzyy
# ────────
# xyxxyzyy
# -- ->remove adjacent xx
# xyyzyy
# -- ->remove adjacent yy
# xzyy
# -- ->remove adjacent yy
# ----------------------------------
# xz <-- Result
task.removeAdjacentDup("xyxxyzyy")
# Example B
# abccebbec
# ─────────
# abccebbec
# -- ->remove adjacent cc
# abebbec
# -- ->remove adjacent bb
# abeec
# -- ->remove adjacent ee
# ----------------------------------
# abc <-- Result
task.removeAdjacentDup("abccebbec")
# Example C
# abcccb
# ─────────
# abcccb
# --- ->remove adjacent ccc
# abb
# -- ->remove adjacent bb
# ----------------------------------
# a <-- Result
task.removeAdjacentDup("abcccb")
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
{
// Add unique adjacent
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
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
task.removeAdjacentDup("xyxxyzyy");
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
task.removeAdjacentDup("abccebbec");
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
task.removeAdjacentDup("abcccb");
}
}
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
{
func removeAdjacentDup(_ data: String)
{
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
{
// Add unique adjacent
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()
{
let task: Duplicates = Duplicates();
// Test
/*
Example A
xyxxyzyy
────────
xyxxyzyy
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
task.removeAdjacentDup("xyxxyzyy");
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
task.removeAdjacentDup("abccebbec");
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
task.removeAdjacentDup("abcccb");
}
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
{
fun removeAdjacentDup(text: String): Unit
{
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
{
// Add unique adjacent
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
{
val task: Duplicates = Duplicates();
// Test
/*
Example A
xyxxyzyy
────────
xyxxyzyy
-- ->remove adjacent xx
xyyzyy
-- ->remove adjacent yy
xzyy
-- ->remove adjacent yy
----------------------------------
xz <-- Result
*/
task.removeAdjacentDup("xyxxyzyy");
/*
Example B
abccebbec
─────────
abccebbec
-- ->remove adjacent cc
abebbec
-- ->remove adjacent bb
abeec
-- ->remove adjacent ee
----------------------------------
abc <-- Result
*/
task.removeAdjacentDup("abccebbec");
/*
Example C
abcccb
─────────
abcccb
--- ->remove adjacent ccc
abb
-- ->remove adjacent bb
----------------------------------
a <-- Result
*/
task.removeAdjacentDup("abcccb");
}
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.
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