Home » Algorithms

Removing consecutive duplicates from a string

You are given a string. You have to remove all consecutive duplicate characters and print the resultant string in the end.
Submitted by Ritik Aggarwal, on January 08, 2019

Constraints:

    (length of string) < 10000

Example:

    Sample Input 1:
    bbccbb
    
    Sample Output 1:
    After removing consecutive duplicates, the answer is :: bcb

    Sample Input 2:
    aabccbba

    Sample Output 2:
    After removing consecutive duplicates, the answer is :: abcba

Explanation of the problem:

1. Find the length of the input string and create an empty string to the answer and add the first character of the input string to the answer string.
2. Store the 0th character of the string in one character variable (let's name it as first) to store the duplicate character that has already added to the answer string.
3. Start iterating from the first index to the end of the input string.
4. If the current character is different from stored duplicate variable then add it to our answer string and make the current character as a duplicate character.
5. After the whole string has been iterated, return the answer string.

The time complexity of the above code is O(length of string).

C++ Implementation

#include <iostream>
#include <string>
using namespace std;

string removeduplicates(string s){
	int n = s.length();
	string ans = "";
	// Adding the first character to the ans
	ans = ans + s[0];
	// first is the character to keep the track of included character
	char first = s[0];
	for(int i = 1;i<n;i++){
		// ch is the current character
		char ch = s[i];
		/* if already included character is different from our 
		current character then add current character to the ans
		and assign current character to included character */
		if(ch != first){
			ans = ans + s[i];
			first = s[i];
		}       
	}
	return ans;
}

// Driver programm to check the code
int main() {
	string s1 ;
	cout<<"Enter string: ";
	cin >>s1;
	cout<<"Entered string is: "<<s1<<endl;	
	cout<<"After removing consecutive duplicates, string: " << removeduplicates(s1) << endl;
}

Output

Enter string: bbccbb
Entered string is: bbccbb
After removing consecutive duplicates, string: bcb