Remove All Adjacent Duplicates In String

Problem

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Constraints

• 1 <= s.length <= 105
• s consists of lowercase English letters.

Solution

The problem Remove All Adjacent Duplicates In String can be solved by pushing each characters in the string s in stack and comparing the top of the stack with the consecutive character.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    string removeDuplicates(string s)
    {
        string ret{s[0]};
        for (int i = 1; i < s.length(); i++)
        {
            if (!ret.empty() && s[i] == ret.back())
                ret.pop_back();
            else
                ret += s[i];
        }

        return ret;
    }
};