1
#define pp pair<int, char>
2

3
class Solution {
4
 public:
5
  string removeDuplicates(string s, int k) {
6
    int n = s.size();
7

8
    stack<pp> stk;
9

10
    int i = 0;
11

12
    while (i < n) {
13
      int count = 1;
14

15
      char ch = s[i];
16

17
      while ((i + 1) < n && s[i] == s[i + 1]) {
18
        i++;
19
        count++;
20
      }
21

22
      int c = 0;
23

24
      if (!stk.empty() && stk.top().second == ch) {
25
        c += stk.top().first;
26
        stk.pop();
27
      }
28

29
      count += c;
30

31
      count = count % k;
32

33
      if (count != 0) {
34
        stk.push({count, ch});
35
      }
36

37
      i++;
38
    }
39

40
    string str = "";
41

42
    while (!stk.empty()) {
43
      int count = stk.top().first;
44

45
      while (count--) {
46
        str.push_back(stk.top().second);
47
      }
48

49
      stk.pop();
50
    }
51

52
    reverse(str.begin(), str.end());
53

54
    return str;
55
  }
56
};