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:
-
Test Case 1: Given Text = "zxxxxxzyyyzz" After removing three consecutive duplicate characters, the modified string is "zxx".
-
Test Case 2: Given Text = "xxyzzzyyxx" After removing three consecutive duplicate characters, the modified string is "x".
-
Test Case 3: Given Text = "xxzzzyyyx" After removing three consecutive duplicate characters, the modified string is an empty string ("").
-
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:
- 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 thetext
as it is. - The algorithm uses two pointers,
size
andauxiliary
, both initialized to the last index of thetext
. - The algorithm defines a boolean variable
task
to indicate whether any three consecutive duplicate characters have been removed and two stringsresult
andtemp
. - The variable
counter
is used to keep track of the number of consecutive duplicate characters encountered. - The algorithm enters a loop that iterates until
size
becomes less than 0. - Inside the loop, the algorithm checks if the character at index
auxiliary
is equal to the character at indexsize
. If they are the same, it means a consecutive duplicate character is found, and thesize
pointer moves back to the previous character. The character is appended to thetemp
string, and thecounter
is incremented. - If the
counter
is not equal to 3, it means there are less than three consecutive duplicates, and thetemp
string is added to the beginning of theresult
string. - If three consecutive duplicates were found (
counter == 3
), thetask
variable is set to true to indicate that thetext
is modified. - The
auxiliary
pointer is updated to the currentsize
. - After the loop, the algorithm checks if any modifications were made (
task == true
). If so, it recursively calls itself with theresult
as the newtext
. - 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:
- For
text = "zxxxxxzyyyzz"
, the modified text is "zxx". - For
text = "xxyzzzyyxx"
, the modified text is "x". - For
text = "xxzzzyyyx"
, the modified text is an empty string (""). - 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.
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