/*

  LeetCode 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.

Example 1:
  Input: s = "abcd", k = 2
  Output: "abcd"
  Explanation: There's nothing to delete.

Example 2:
  Input: s = "deeedbbcccbdaa", k = 3
  Output: "aa"
  Explanation:
  First delete "eee" and "ccc", get "ddbbbdaa"
  Then delete "bbb", get "dddaa"
  Finally delete "ddd", get "aa"

Example 3:
  Input: s = "pbbcggttciiippooaais", k = 2
  Output: "ps"

Constraints:
  1 <= s.length <= 105
  2 <= k <= 104
  s only contains lowercase English letters.

Hint 1 Use a stack to store the characters, when there are k same characters, delete them.
  Hint 2 To make it more efficient, use a pair to store the value and the count of each
  character.

  deeedbbcccbdaa
  --------------
  push
  ----
  d
  eee -> pop
  d
  bb
  ccc -> pop
  b   -> pop
  d   -> pop
  a
  a
  ==> "aa" 
 */

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

class Solution {
public:
    string removeDuplicates(string s, int k)
    {
        vector<pair<char,int>> stk;

        // loop over string pushing pair<char, int> onto stack
        for (char c: s)
        {
            if (!stk.empty() && stk.back().first == c) // same char, pop if count reaches k
            {
                if (++(stk.back().second) == k)
                    stk.pop_back();
            }
            else
            {
                stk.emplace_back(c, 1);
            }
        }

        cout << "stack: "; for (auto& p: stk) cout << p.first;
        cout << endl;
        
        string result;
        for (auto& p: stk)
        {
            // create string  with cnt of char
            string s(p.second, p.first);
            result += s;
        }
        return result;
    }
};


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

    Solution s;

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

    return 0;
}