Skip to main content

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;
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).

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