题目

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

  1. 输入：s = "abcd", k = 2
  2. 输出："abcd"
  3. 解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

示例 3：

输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

提示：

  • 1 <= s.length <= 10^5
  • 2 <= k <= 10^4

  • s 中只含有小写英文字母。

    解题方法

    栈

    使用栈记录重复字符个数，达到k后通过erase函数删除。
    时间复杂度O(n)，空间复杂度O(n)。
    C++代码：

    class Solution {
public:
  string removeDuplicates(string s, int k) {
      stack<int> num;
      for(int i = 0; i<s.size(); i++) {
          if(i!=0 && s[i]==s[i-1]) {
              if(++num.top()==k) {
                  num.pop();
                  s.erase(i-k+1, k);
                  i = i-k;
              }
          }
          else    num.push(1);
      }

      return s;
  }
};

    栈重建

    使用两个栈分别记录重复元素及重复个数，若个数达到k则将两个栈顶弹出，最后通过两个栈重构字符串
    避免调用erase函数。
    C++代码：

    class Solution {
public:
  string removeDuplicates(string s, int k) {
      stack<int> num;
      stack<char> tmp;
      for(char ch : s) {
          if(!tmp.empty() && ch==tmp.top()) {
              if(++num.top()==k) {
                  num.pop();
                  tmp.pop();
              }
          }
          else {
              num.push(1);
              tmp.push(ch);
          }   
      }

      string result = "";
      while(!num.empty()) {
          while(num.top()--) {
              result += tmp.top();
          }
          num.pop();
          tmp.pop();
      }
      reverse(result.begin(), result.end());

      return result;
  }
};

    双指针

    使用双指针直接对字符串进行操作，避免上一方法中的字符串重构。
    C++代码：

    class Solution {
public:
  string removeDuplicates(string s, int k) {
      stack<int> num;
      int j = 0;
      for(int i = 0; i<s.size(); i++, j++) {
          s[j] = s[i];
          if(j!=0 && s[j]==s[j-1]) {
              if(++num.top()==k) {
                  num.pop();
                  j = j-k;
              }
          }
          else {
              num.push(1);
          }   
      }

      return s.substr(0, j);
  }
};

    改进的双指针法

    避免使用队列记录重复元素个数，使用双指针遍历数组，当指针移动前后元素不同时，对中间的重复字符进行删除。
    空间复杂度降为O(1)。
    C++代码：

    class Solution {
public:
  string removeDuplicates(string _s, int k) {
      char *d, *t, *b, *u, *s;
      d = t = b = s = (char*)_s.c_str();
      while (*d) {
          *t++ = *d++;
          if (*d != *(t - 1)) {
              while (t - s >= k) {
                  b = u = t - 1;
                  while (u - b < k && *b == *u)
                      --b;
                  if (u - b < k)
                      break;
                  t = t - k;
              }
          }
      }
      *t = *d;
      return s;
  }
};