/*
  Problem 1209. Remove All Adjacent Duplicates in String II
  Medium

  You are given a string s and an integer k, a k duplicate removal
  consists of choosing k adjacent and equal letters from s and
  removing them, causing the left and the right side of the deleted
  substring to concatenate together.
  
  We repeatedly make k duplicate removals on s until we no longer can.
  
  Return the final string after all such duplicate removals have been
  made. It is guaranteed that the answer is unique.
 */

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string removeDuplicates(string s, int k) {
        deque<pair<int, char>> stack;
        for (int i = 0; i < (int)s.size(); ++i) {
            if (stack.empty() || s.at(i) != stack.front().second)
            {
                stack.push_front({ 1, s.at(i) });
            }
            else
            {
                // s.at(i) == top of stack
                if (++stack.front().first == k)
                    stack.pop_front();
            }
        }
        
        string result;        
        while (!stack.empty()) {
            result += string(stack.back().first, stack.back().second);
            stack.pop_back();            
        }
        return result;
    }
};

int main(void)
{
    vector<tuple<string,int,string>> testCases = {
        {"abcd",2,"abcd"},
        {"deeedbbcccbdaa",3,"aa"},
        {"pbbcggttciiippooaais",2,"ps"},
    };

    for (auto tc: testCases)
    {
        Solution s;
        string str = get<0>(tc);
        int k = get<1>(tc);
        string expected = get<2>(tc);
        
        string result = s.removeDuplicates(str, k);
        cout << "   input: " << str << endl;        
        cout << "  result: " << result << endl;
        cout << "expected: " << expected << endl;
        cout << "-----------------------\n";
    }
}