Skip to main content

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

Last updated on by Kalkicode




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.

New Comment