1209. Remove All Adjacent Duplicates in String II

Leetcode link

解题思路

题目要求我们去掉字符串重复 k 次的字符，需要注意的是每次删除完字符之后还要重新检查新的字符串是否还存在重复 k 次的字符

我们可以用栈来做这道题，栈内存放 字符 - 连续出现个数 的集合，当连续出现个数等于 k 的时候，就可以把这一组集合出栈了

最后，我们根据栈内的信息重新还原字符串就好

C++

class Solution {
 public:
  string removeDuplicates(string s, int k) {
    stack<pair<char, int>> st;
    for (int i = 0; i < s.size(); i++) {
      int count = 1;
      while ((i + 1 < s.size()) && (s[i] == s[i + 1])) {
        i++;
        count++;
      }
      // 考虑到当前栈顶可能有一样的字符，也要一起计算次数
      while (!st.empty() && st.top().first == s[i]) {
        count += st.top().second;
        st.pop();
      }
      // 取个余，等于把其他部分删掉了
      count %= k;
      if (count > 0) {
        st.push({s[i], count});
      }
    }
    // 最后根据栈内信息还原字符串
    string res = "";
    while (!st.empty()) {
      auto top = st.top();
      while (top.second-- > 0) {
        res += top.first;
      }
      st.pop();
    }
    reverse(res.begin(), res.end());
    return res;
  }
};

Javascript

var removeDuplicates = function(s, k) {
    let stack = [];
    for (let i = 0; i < s.length; i++) {
      let count = 1;
      while ((i + 1 < s.length) && (s[i] == s[i + 1])) {
        i++;
        count++;
      }
      // 考虑到当前栈顶可能有一样的字符，也要一起计算次数
      while (stack.length!==0 && stack[stack.length-1][0] == s[i]) {
        count += stack[stack.length-1][1];
        stack.pop();
      }
      // 取个余，等于把其他部分删掉了
      count %= k;
      if (count > 0) {
        stack.push([s[i], count]);
      }
    }
  // 最后根据栈内信息还原字符串
    let res = "";
    while (stack.length!==0) {
      let [ch, count] = stack[stack.length-1];
      while (count-- > 0) {
        res = ch + res;
      }
      stack.pop();
    }
    return res;
};