aboutsummaryrefslogtreecommitdiff
path: root/remove_adjacent_dup.cpp
blob: c0cc3411fd8d9a4931359d8c6a4adc5cb24d5903 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include "leetcode.h"

class Solution {
public:
  string removeDuplicates(string s, int k) {
    //      cout << s << endl << k << endl;
    if (s.size() < k)
      return s;
    stack<pair<char, int>> stk;
    for (int i = 0; i < s.size(); ++i) {
      if (stk.empty() || stk.top().first != s[i])
        stk.push({s[i], 1});
      else {
        auto prev = stk.top();
        stk.pop();
        stk.push({s[i], prev.second + 1});
      }
      if (stk.top().second == k)
        stk.pop();
    }
    string ans = "";
    while (!stk.empty()) {
      auto curr = stk.top();
      stk.pop();
      while (curr.second--)
        ans.push_back(curr.first);
    }
    reverse(ans.begin(), ans.end());
    //      cout << ans;
    return ans;
  }
};

int main() {
  Solution obj;
  obj.removeDuplicates("deeedbbcccbdaa", 3);
}