Stack: Remove All Adjacent Duplicates In String

Problem Statement:

Given a string, remove all adjecent duplicate characters.

Example

Input: s = “abbaca”
Output: “ca”

Solution

You need to use a stack for the solution.
Insert characters from the string one by one.

Then if the next character is sa,e as the last character in res, then pop the last char form the res.

If the next char is different, then we append it to the end of res.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

string remove_duplicates(string S) 
{
    string res = "";
    for (char& c : S)
        if (res.size() && c == res.back())
            res.pop_back();
        else
            res.push_back(c);
    return res;
}

int main()
{ 
    string s = "abbaca";

    cout<<"The string after removing duplicate is "<<remove_duplicates(s)<<endl;

    return 0;

}

Output:

The string after removing duplicate is ca

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *