Remove Consecutive Duplicates From A String in C++

Filed Under: C++
Remove Consecutive Duplicates From A String

In this article, we will learn to remove consecutive duplicates from a string using C++. This type of problem is very common for technical interviews or screening rounds.

Today we will approach this problem using a linear time algorithm and will further write a C++ program to test it for different inputs. So without wasting time, let’s get started.

Problem Statement

You are given a finite length string as input. You have to remove all the consecutive duplicates from the given string.

Test cases:

Case 1:
Input string: aaabbc
Output string: abc

Case 2:
Input string: abcabcacaab
Output string: abcabcacab

Case 3:
Input string: ''
Output string: ''

Concept of Consecutive Duplicates

The solution to this problem is very simple. We would traverse the string and remove all the duplicates in one go. Below are the steps that we would follow to code the algorithm

  • Base case: Check if the length of the vector is less than or equal to one
    • If so, then simply return from the function because an empty or a single character string doesn’t contain any duplicates.
  • Otherwise, start a for loop and initialize a variable prev = 0
    • This for loop would run from i = 1 to i = len_of_string
    • At each position we will perform some checks and modify the string accordingly
      • If the value of str[prev] == str[current]
        • Do nothing, just increment the value of current
      • Else, do prev++ and str[prev] = str[current]
        • In this case, the second step is the most important step

Algorithm for Removing Consecutive Duplicates

void remove_duplicates(vector <char> &str)
{
	int len = str.size();

	// base case
	// if the string is empty or
	// single character string
	if(len <= 1)
		return;

	// otherwise
	int prev = 0;

	for(int current = 1; current < len; current++)
	{
		// if the next character is the same as
		// the previous character
		// simply increment the previous
		// and update str[previous] as
		// str[current]
		if(str[current] != str[prev])
		{
			prev++;
			str[prev] = str[current];
		}
	}

	// now terminate the string with a NULL character
	str[prev + 1] = '\0';

	return;
}
Algorithm 7
Algorithm

Time And Space Complexity Analysis

As you can notice, our algorithm uses no additional space, i.e. the overall space complexity is O(1). The worst-case time complexity on the other hand is linear because we are traversing over the whole string just once. During each iteration, we have done some constant time work. Hence the time complexity boils down to O(N). Where N is the length of the string.

C++ Program To Test The Working Of The Algorithm for Removing Consecutive Duplicates

#include <iostream>
#include <vector>

using namespace std;

// algorithm to remove consecutive duplicates from a string
void remove_duplicates(vector <char> &str)
{
	int len = str.size();

	// base case
	// if the string is empty or
	// single character string
	if(len <= 1)
		return;

	// otherwise
	int prev = 0;

	for(int current = 1; current < len; current++)
	{
		// if the next character is the same as
		// the previous character
		// simply increment the previous
		// and update str[previous] as
		// str[current]
		if(str[current] != str[prev])
		{
			prev++;
			str[prev] = str[current];
		}
	}

	// now terminate the string with a NULL character
	str[prev + 1] = '\0';

	return;
}

int main()
{
	cout << "Enter the string, press ! to stop" << endl;
	vector <char> str;

	// take the input
	while(true)
	{
		char ch;
		cin >> ch;
		
		if(ch == '!')
			break;

		str.push_back(ch);
	}

	remove_duplicates(str);

	cout << "The string after removing the duplicates is:" << endl;
	
	for(int i = 0; str[i] != '\0'; i++)
		cout << str[i] << " ";
	cout << endl;

	return 0;
}
Remove Consecutive Duplicates Driver Code
Remove Consecutive Duplicates Driver Code

Output

Consecutive Duplicates Output
Consecutive Duplicates Output

Conclusion

In this article, we learned how to remove consecutive duplicates from a given string of finite length. First, we looked at the problem statement, later we understood the concept. In the end, we coded the algorithm in C++ and tested its work for different test cases. That’s it for today, thanks for reading.

Further Readings

To learn more about string algorithms and vectors, you can refer to the following articles.

https://www.journaldev.com/59833/generate-strings-from-codes-cpp

https://www.journaldev.com/59506/generate-balanced-brackets-recursion-cpp

https://www.journaldev.com/59322/find-subsets-bit-masking

close
Generic selectors
Exact matches only
Search in title
Search in content