Posted on by Kalkicode
Code Recursion

Remove three consecutive duplicates from string

The problem is to remove all occurrences of three consecutive duplicate characters from a given string. The task is to modify the string in such a way that any sequence of three consecutive identical characters is removed from the string. The modified string is then returned as the output.

Explanation using Example

Let's consider the test cases from the provided code:

  1. Test Case 1: Given Text = "zxxxxxzyyyzz" After removing three consecutive duplicate characters, the modified string is "zxx".

  2. Test Case 2: Given Text = "xxyzzzyyxx" After removing three consecutive duplicate characters, the modified string is "x".

  3. Test Case 3: Given Text = "xxzzzyyyx" After removing three consecutive duplicate characters, the modified string is an empty string ("").

  4. Test Case 4: Given Text = "xxzyyx" After removing three consecutive duplicate characters, the modified string is "xxzyyx".

Pseudocode

removeThreeConsecutiveDuplicate(text)
    if text length is less than 2
        return text
    size = text length - 1
    task = false
    auxiliary = size
    result = ""
    temp = ""
    counter = 0
    while size >= 0
        while size >= 0 and counter < 3 and text[auxiliary] == text[size]
            temp = text[size] + temp
            counter++
            size--
        if counter is not equal to 3
            result = temp + result
        else
            task = true
        auxiliary = size
        counter = 0
        temp = ""
    if task is true
        return removeThreeConsecutiveDuplicate(result)
    return result

removeAdjacent(text)
    print "Given Text : text"
    print "Output     : removeThreeConsecutiveDuplicate(text)"

Algorithm Explanation

The removeThreeConsecutiveDuplicate function is a recursive algorithm to remove three consecutive duplicate characters from the given text using the following steps:

  1. If the length of the text is less than 2, it means there are not enough characters to form a sequence of three consecutive duplicates. In this case, the function returns the text as it is.
  2. The algorithm uses two pointers, size and auxiliary, both initialized to the last index of the text.
  3. The algorithm defines a boolean variable task to indicate whether any three consecutive duplicate characters have been removed and two strings result and temp.
  4. The variable counter is used to keep track of the number of consecutive duplicate characters encountered.
  5. The algorithm enters a loop that iterates until size becomes less than 0.
  6. Inside the loop, the algorithm checks if the character at index auxiliary is equal to the character at index size. If they are the same, it means a consecutive duplicate character is found, and the size pointer moves back to the previous character. The character is appended to the temp string, and the counter is incremented.
  7. If the counter is not equal to 3, it means there are less than three consecutive duplicates, and the temp string is added to the beginning of the result string.
  8. If three consecutive duplicates were found (counter == 3), the task variable is set to true to indicate that the text is modified.
  9. The auxiliary pointer is updated to the current size.
  10. After the loop, the algorithm checks if any modifications were made (task == true). If so, it recursively calls itself with the result as the new text.
  11. If no modifications were made, the algorithm returns the result.

The removeAdjacent function handles the request to remove three consecutive duplicate characters from the given text. It first prints the given text and then prints the modified text obtained from the removeThreeConsecutiveDuplicate function.

Code Solution

Here given code implementation process.

/*
  Java Program for
  Remove three consecutive duplicates from string
*/
public class RemoveCharacters
{
	public String removeThreeConsecutiveDuplicate(String text)
	{
		if (text.length() < 2)
		{
			return text;
		}
		// Define some auxiliary variable
		int size = text.length() - 1;
		boolean task = false;
		int auxiliary = size;
		String result = "";
		String temp = "";
		int counter = 0;
		// Execute loop until when size is less than two
		while (size >= 0)
		{
			// Skip similar 3 adjacent characters
			while (size >= 0 && counter < 3 && text.charAt(auxiliary) == text.charAt(size))
			{
				temp = text.charAt(size) + temp;
				counter++;
				size--;
			}
			if (counter != 3)
			{
				// When adjacent are not same 
				// Then add new character at beginning of result
				result = temp + result;
			}
			else
			{
				task = true;
			}
			// Get new index
			auxiliary = size;
			counter = 0;
			temp = "";
		}
		if (task == true)
		{
			return removeThreeConsecutiveDuplicate(result);
		}
		return result;
	}
	// Handles the request to printing calculate result
	public void removeAdjacent(String text)
	{
		System.out.println(" Given Text : " + text);
		System.out.println(" Output     : " + removeThreeConsecutiveDuplicate(text));
	}
	public static void main(String[] args)
	{
		RemoveCharacters test = new RemoveCharacters();
		// Test Cases
		test.removeAdjacent("zxxxxxzyyyzz");
		test.removeAdjacent("xxyzzzyyxx");
		test.removeAdjacent("xxzzzyyyx");
		test.removeAdjacent("xxzyyx");
	}
}

input

 Given Text : zxxxxxzyyyzz
 Output     : zxx
 Given Text : xxyzzzyyxx
 Output     : x
 Given Text : xxzzzyyyx
 Output     :
 Given Text : xxzyyx
 Output     : xxzyyx
// Include header file
#include <iostream>

#include <string>

using namespace std;
/*
  C++ Program for
  Remove three consecutive duplicates from string
*/
class RemoveCharacters
{
	public: string removeThreeConsecutiveDuplicate(string text)
	{
		if (text.length() < 2)
		{
			return text;
		}
		// Define some auxiliary variable
		int size = text.length() - 1;
		bool task = false;
		int auxiliary = size;
		string result = "";
		string temp = "";
		int counter = 0;
		// Execute loop until when size is less than two
		while (size >= 0)
		{
			// Skip similar 3 adjacent characters
			while (size >= 0 && counter < 3 && text[auxiliary] == text[size])
			{
				temp = text[size] + temp;
				counter++;
				size--;
			}
			if (counter != 3)
			{
				// When adjacent are not same 
				// Then add new character at beginning of result
				result = temp + result;
			}
			else
			{
				task = true;
			}
			// Get new index
			auxiliary = size;
			counter = 0;
			temp = "";
		}
		if (task == true)
		{
			return this->removeThreeConsecutiveDuplicate(result);
		}
		return result;
	}
	// Handles the request to printing calculate result
	void removeAdjacent(string text)
	{
		cout << " Given Text : " << text << endl;
		cout << " Output     : " << this->removeThreeConsecutiveDuplicate(text) << endl;
	}
};
int main()
{
	RemoveCharacters *test = new RemoveCharacters();
	// Test Cases
	test->removeAdjacent("zxxxxxzyyyzz");
	test->removeAdjacent("xxyzzzyyxx");
	test->removeAdjacent("xxzzzyyyx");
	test->removeAdjacent("xxzyyx");
	return 0;
}

input

 Given Text : zxxxxxzyyyzz
 Output     : zxx
 Given Text : xxyzzzyyxx
 Output     : x
 Given Text : xxzzzyyyx
 Output     :
 Given Text : xxzyyx
 Output     : xxzyyx
// Include namespace system
using System;
/*
  Csharp Program for
  Remove three consecutive duplicates from string
*/
public class RemoveCharacters
{
	public String removeThreeConsecutiveDuplicate(String text)
	{
		if (text.Length < 2)
		{
			return text;
		}
		// Define some auxiliary variable
		int size = text.Length - 1;
		Boolean task = false;
		int auxiliary = size;
		String result = "";
		String temp = "";
		int counter = 0;
		// Execute loop until when size is less than two
		while (size >= 0)
		{
			// Skip similar 3 adjacent characters
			while (size >= 0 && counter < 3 && text[auxiliary] == text[size])
			{
				temp = text[size] + temp;
				counter++;
				size--;
			}
			if (counter != 3)
			{
				// When adjacent are not same 
				// Then add new character at beginning of result
				result = temp + result;
			}
			else
			{
				task = true;
			}
			// Get new index
			auxiliary = size;
			counter = 0;
			temp = "";
		}
		if (task == true)
		{
			return this.removeThreeConsecutiveDuplicate(result);
		}
		return result;
	}
	// Handles the request to printing calculate result
	public void removeAdjacent(String text)
	{
		Console.WriteLine(" Given Text : " + text);
		Console.WriteLine(" Output     : " + this.removeThreeConsecutiveDuplicate(text));
	}
	public static void Main(String[] args)
	{
		RemoveCharacters test = new RemoveCharacters();
		// Test Cases
		test.removeAdjacent("zxxxxxzyyyzz");
		test.removeAdjacent("xxyzzzyyxx");
		test.removeAdjacent("xxzzzyyyx");
		test.removeAdjacent("xxzyyx");
	}
}

input

 Given Text : zxxxxxzyyyzz
 Output     : zxx
 Given Text : xxyzzzyyxx
 Output     : x
 Given Text : xxzzzyyyx
 Output     :
 Given Text : xxzyyx
 Output     : xxzyyx
<?php
/*
  Php Program for
  Remove three consecutive duplicates from string
*/
class RemoveCharacters
{
	public	function removeThreeConsecutiveDuplicate($text)
	{
		if (strlen($text) < 2)
		{
			return $text;
		}
		// Define some auxiliary variable
		$size = strlen($text) - 1;
		$task = false;
		$auxiliary = $size;
		$result = "";
		$temp = "";
		$counter = 0;
		// Execute loop until when size is less than two
		while ($size >= 0)
		{
			// Skip similar 3 adjacent characters
			while ($size >= 0 && $counter < 3 && $text[$auxiliary] == $text[$size])
			{
				$temp = $text[$size].$temp;
				$counter++;
				$size--;
			}
			if ($counter != 3)
			{
				// When adjacent are not same 
				// Then add new character at beginning of result
				$result = $temp.$result;
			}
			else
			{
				$task = true;
			}
			// Get new index
			$auxiliary = $size;
			$counter = 0;
			$temp = "";
		}
		if ($task == true)
		{
			return $this->removeThreeConsecutiveDuplicate($result);
		}
		return $result;
	}
	// Handles the request to printing calculate result
	public	function removeAdjacent($text)
	{
		echo " Given Text : ".$text.
		"\n";
		echo " Output     : ".$this->removeThreeConsecutiveDuplicate($text).
		"\n";
	}
}

function main()
{
	$test = new RemoveCharacters();
	// Test Cases
	$test->removeAdjacent("zxxxxxzyyyzz");
	$test->removeAdjacent("xxyzzzyyxx");
	$test->removeAdjacent("xxzzzyyyx");
	$test->removeAdjacent("xxzyyx");
}
main();

input

 Given Text : zxxxxxzyyyzz
 Output     : zxx
 Given Text : xxyzzzyyxx
 Output     : x
 Given Text : xxzzzyyyx
 Output     :
 Given Text : xxzyyx
 Output     : xxzyyx
/*
  Node JS Program for
  Remove three consecutive duplicates from string
*/
class RemoveCharacters
{
	removeThreeConsecutiveDuplicate(text)
	{
		if (text.length < 2)
		{
			return text;
		}
		// Define some auxiliary variable
		var size = text.length - 1;
		var task = false;
		var auxiliary = size;
		var result = "";
		var temp = "";
		var counter = 0;
		// Execute loop until when size is less than two
		while (size >= 0)
		{
			// Skip similar 3 adjacent characters
			while (size >= 0 && counter < 3 && text.charAt(auxiliary) == text.charAt(size))
			{
				temp = text.charAt(size) + temp;
				counter++;
				size--;
			}
			if (counter != 3)
			{
				// When adjacent are not same 
				// Then add new character at beginning of result
				result = temp + result;
			}
			else
			{
				task = true;
			}
			// Get new index
			auxiliary = size;
			counter = 0;
			temp = "";
		}
		if (task == true)
		{
			return this.removeThreeConsecutiveDuplicate(result);
		}
		return result;
	}
	// Handles the request to printing calculate result
	removeAdjacent(text)
	{
		console.log(" Given Text : " + text);
		console.log(" Output     : " + this.removeThreeConsecutiveDuplicate(text));
	}
}

function main()
{
	var test = new RemoveCharacters();
	// Test Cases
	test.removeAdjacent("zxxxxxzyyyzz");
	test.removeAdjacent("xxyzzzyyxx");
	test.removeAdjacent("xxzzzyyyx");
	test.removeAdjacent("xxzyyx");
}
main();

input

 Given Text : zxxxxxzyyyzz
 Output     : zxx
 Given Text : xxyzzzyyxx
 Output     : x
 Given Text : xxzzzyyyx
 Output     :
 Given Text : xxzyyx
 Output     : xxzyyx
#  Python 3 Program for
#  Remove three consecutive duplicates from string
class RemoveCharacters :
	def removeThreeConsecutiveDuplicate(self, text) :
		if (len(text) < 2) :
			return text
		
		size = len(text) - 1
		task = False
		auxiliary = size
		result = ""
		temp = ""
		counter = 0
		#  Execute loop until when size is less than two
		while (size >= 0) :
			#  Skip similar 3 adjacent characters
			while (size >= 0 and counter < 3 and text[auxiliary] == text[size]) :
				temp = text[size] + temp
				counter += 1
				size -= 1
			
			if (counter != 3) :
				#  When adjacent are not same 
				#  Then add new character at beginning of result
				result = temp + result
			else :
				task = True
			
			#  Get new index
			auxiliary = size
			counter = 0
			temp = ""
		
		if (task == True) :
			return self.removeThreeConsecutiveDuplicate(result)
		
		return result
	
	#  Handles the request to printing calculate result
	def removeAdjacent(self, text) :
		print(" Given Text : ", text)
		print(" Output     : ", self.removeThreeConsecutiveDuplicate(text))
	

def main() :
	test = RemoveCharacters()
	#  Test Cases
	test.removeAdjacent("zxxxxxzyyyzz")
	test.removeAdjacent("xxyzzzyyxx")
	test.removeAdjacent("xxzzzyyyx")
	test.removeAdjacent("xxzyyx")

if __name__ == "__main__": main()

input

 Given Text :  zxxxxxzyyyzz
 Output     :  zxx
 Given Text :  xxyzzzyyxx
 Output     :  x
 Given Text :  xxzzzyyyx
 Output     :
 Given Text :  xxzyyx
 Output     :  xxzyyx
#  Ruby Program for
#  Remove three consecutive duplicates from string
class RemoveCharacters 
	def removeThreeConsecutiveDuplicate(text) 
		if (text.length < 2) 
			return text
		end

		#  Define some auxiliary variable
		size = text.length - 1
		task = false
		auxiliary = size
		result = ""
		temp = ""
		counter = 0
		#  Execute loop until when size is less than two
		while (size >= 0) 
			#  Skip similar 3 adjacent characters
			while (size >= 0 && counter < 3 && text[auxiliary] == text[size]) 
				temp = text[size] + temp
				counter += 1
				size -= 1
			end

			if (counter != 3) 
				#  When adjacent are not same 
				#  Then add new character at beginning of result
				result = temp + result
			else 
				task = true
			end

			#  Get new index
			auxiliary = size
			counter = 0
			temp = ""
		end

		if (task == true) 
			return self.removeThreeConsecutiveDuplicate(result)
		end

		return result
	end

	#  Handles the request to printing calculate result
	def removeAdjacent(text) 
		print(" Given Text : ", text, "\n")
		print(" Output     : ", self.removeThreeConsecutiveDuplicate(text), "\n")
	end

end

def main() 
	test = RemoveCharacters.new()
	#  Test Cases
	test.removeAdjacent("zxxxxxzyyyzz")
	test.removeAdjacent("xxyzzzyyxx")
	test.removeAdjacent("xxzzzyyyx")
	test.removeAdjacent("xxzyyx")
end

main()

input

 Given Text : zxxxxxzyyyzz
 Output     : zxx
 Given Text : xxyzzzyyxx
 Output     : x
 Given Text : xxzzzyyyx
 Output     : 
 Given Text : xxzyyx
 Output     : xxzyyx
/*
  Scala Program for
  Remove three consecutive duplicates from string
*/
class RemoveCharacters()
{
	def removeThreeConsecutiveDuplicate(text: String): String = {
		if (text.length() < 2)
		{
			return text;
		}
		// Define some auxiliary variable
		var size: Int = text.length() - 1;
		var task: Boolean = false;
		var auxiliary: Int = size;
		var result: String = "";
		var temp: String = "";
		var counter: Int = 0;
		// Execute loop until when size is less than two
		while (size >= 0)
		{
			// Skip similar 3 adjacent characters
			while (size >= 0 && counter < 3 && text.charAt(auxiliary) == text.charAt(size))
			{
				temp = "" + text.charAt(size) + temp;
				counter += 1;
				size -= 1;
			}
			if (counter != 3)
			{
				// When adjacent are not same 
				// Then add new character at beginning of result
				result = temp + result;
			}
			else
			{
				task = true;
			}
			// Get new index
			auxiliary = size;
			counter = 0;
			temp = "";
		}
		if (task == true)
		{
			return removeThreeConsecutiveDuplicate(result);
		}
		return result;
	}
	// Handles the request to printing calculate result
	def removeAdjacent(text: String): Unit = {
		println(" Given Text : " + text);
		println(" Output     : " + removeThreeConsecutiveDuplicate(text));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var test: RemoveCharacters = new RemoveCharacters();
		// Test Cases
		test.removeAdjacent("zxxxxxzyyyzz");
		test.removeAdjacent("xxyzzzyyxx");
		test.removeAdjacent("xxzzzyyyx");
		test.removeAdjacent("xxzyyx");
	}
}

input

 Given Text : zxxxxxzyyyzz
 Output     : zxx
 Given Text : xxyzzzyyxx
 Output     : x
 Given Text : xxzzzyyyx
 Output     :
 Given Text : xxzyyx
 Output     : xxzyyx
/*
  Swift 4 Program for
  Remove three consecutive duplicates from string
*/
class RemoveCharacters
{
	func removeThreeConsecutiveDuplicate(_ t: String) -> String
	{
      	let text = Array(t);
		if (text.count < 2)
		{
			return t;
		}
		// Define some auxiliary variable
		var size: Int = text.count - 1;
		var task: Bool = false;
		var auxiliary: Int = size;
		var result: String = "";
		var temp: String = "";
		var counter: Int = 0;
		// Execute loop until when size is less than two
		while (size >= 0)
		{
			// Skip similar 3 adjacent characters
			while (size >= 0 && counter < 3 && text[auxiliary] == text[size])
			{
				temp = String(text[size]) + temp;
				counter += 1;
				size -= 1;
			}
			if (counter  != 3)
			{
				// When adjacent are not same 
				// Then add new character at beginning of result
				result = temp + result;
			}
			else
			{
				task = true;
			}
			// Get new index
			auxiliary = size;
			counter = 0;
			temp = "";
		}
		if (task == true)
		{
			return self.removeThreeConsecutiveDuplicate(result);
		}
		return result;
	}
	// Handles the request to printing calculate result
	func removeAdjacent(_ text: String)
	{
		print(" Given Text : ", text);
		print(" Output     : ", self.removeThreeConsecutiveDuplicate(text));
	}
}
func main()
{
	let test: RemoveCharacters = RemoveCharacters();
	// Test Cases
	test.removeAdjacent("zxxxxxzyyyzz");
	test.removeAdjacent("xxyzzzyyxx");
	test.removeAdjacent("xxzzzyyyx");
	test.removeAdjacent("xxzyyx");
}
main();

input

 Given Text :  zxxxxxzyyyzz
 Output     :  zxx
 Given Text :  xxyzzzyyxx
 Output     :  x
 Given Text :  xxzzzyyyx
 Output     :
 Given Text :  xxzyyx
 Output     :  xxzyyx
/*
  Kotlin Program for
  Remove three consecutive duplicates from string
*/
class RemoveCharacters
{
	fun removeThreeConsecutiveDuplicate(text: String): String
	{
		if (text.length < 2)
		{
			return text;
		}
		// Define some auxiliary variable
		var size: Int = text.length - 1;
		var task: Boolean = false;
		var auxiliary: Int = size;
		var result: String = "";
		var temp: String = "";
		var counter: Int = 0;
		while (size >= 0)
		{
			while (size >= 0 && counter < 3 && text.get(auxiliary) == text.get(size))
			{
				temp = text.get(size) + temp;
				counter += 1;
				size -= 1;
			}
			if (counter != 3)
			{
				// When adjacent are not same 
				// Then add new character at beginning of result
				result = temp + result;
			}
			else
			{
				task = true;
			}
			// Get new index
			auxiliary = size;
			counter = 0;
			temp = "";
		}
		if (task == true)
		{
			return this.removeThreeConsecutiveDuplicate(result);
		}
		return result;
	}
	// Handles the request to printing calculate result
	fun removeAdjacent(text: String): Unit
	{
		println(" Given Text : " + text);
		println(" Output     : " + this.removeThreeConsecutiveDuplicate(text));
	}
}
fun main(args: Array < String > ): Unit
{
	val test: RemoveCharacters = RemoveCharacters();
	// Test Cases
	test.removeAdjacent("zxxxxxzyyyzz");
	test.removeAdjacent("xxyzzzyyxx");
	test.removeAdjacent("xxzzzyyyx");
	test.removeAdjacent("xxzyyx");
}

input

 Given Text : zxxxxxzyyyzz
 Output     : zxx
 Given Text : xxyzzzyyxx
 Output     : x
 Given Text : xxzzzyyyx
 Output     :
 Given Text : xxzyyx
 Output     : xxzyyx

Time Complexity

The time complexity of the provided algorithm depends on the length of the input text. The algorithm performs a linear scan through the characters of the text in the worst case. Therefore, the time complexity is O(n), where n is the length of the text.

Resultant Output Explanation

The code correctly removes all occurrences of three consecutive duplicate characters using recursion for the given test cases:

  1. For text = "zxxxxxzyyyzz", the modified text is "zxx".
  2. For text = "xxyzzzyyxx", the modified text is "x".
  3. For text = "xxzzzyyyx", the modified text is an empty string ("").
  4. For text = "xxzyyx", the modified text is "xxzyyx".

The algorithm efficiently removes three consecutive duplicate characters from the given text using recursion and provides the correct modified text for the provided test cases.

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