5

Remove Consecutive Duplicates From A String in C++

 2 years ago
source link: https://www.journaldev.com/60732/remove-consecutive-duplicates-from-string-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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 7Algorithm

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 CodeRemove Consecutive Duplicates Driver Code

Output

Consecutive Duplicates OutputConsecutive 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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK