Question

1209. 删除字符串中的所有相邻重复项 II

English Version

题目描述

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

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

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

本题答案保证唯一。

 

示例 1：

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

示例 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 中只含有小写英文字母。

解法

方法一：栈

我们可以遍历字符串 $s$，维护一个栈，栈中存储的是字符和该字符出现的次数。当遍历到字符 $c$ 时，如果栈顶元素的字符和 $c$ 相同，则将栈顶元素的次数加一，否则将字符 $c$ 和次数 $1$ 入栈。当栈顶元素的次数等于 $k$ 时，将栈顶元素出栈。

遍历完字符串 $s$ 后，栈中存储的就是最终结果。我们可以将栈中的元素依次弹出，拼接成字符串即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

class Solution:
  def removeDuplicates(self, s: str, k: int) -> str:
    t = []
    i, n = 0, len(s)
    while i < n:
      j = i
      while j < n and s[j] == s[i]:
        j += 1
      cnt = j - i
      cnt %= k
      if t and t[-1][0] == s[i]:
        t[-1][1] = (t[-1][1] + cnt) % k
        if t[-1][1] == 0:
          t.pop()
      elif cnt:
        t.append([s[i], cnt])
      i = j
    ans = [c * v for c, v in t]
    return "".join(ans)

class Solution {
  public String removeDuplicates(String s, int k) {
    Deque<int[]> stk = new ArrayDeque<>();
    for (int i = 0; i < s.length(); ++i) {
      int j = s.charAt(i) - 'a';
      if (!stk.isEmpty() && stk.peek()[0] == j) {
        stk.peek()[1] = (stk.peek()[1] + 1) % k;
        if (stk.peek()[1] == 0) {
          stk.pop();
        }
      } else {
        stk.push(new int[] {j, 1});
      }
    }
    StringBuilder ans = new StringBuilder();
    for (var e : stk) {
      char c = (char) (e[0] + 'a');
      for (int i = 0; i < e[1]; ++i) {
        ans.append(c);
      }
    }
    ans.reverse();
    return ans.toString();
  }
}

class Solution {
public:
  string removeDuplicates(string s, int k) {
    vector<pair<char, int>> stk;
    for (char& c : s) {
      if (stk.size() && stk.back().first == c) {
        stk.back().second = (stk.back().second + 1) % k;
        if (stk.back().second == 0) {
          stk.pop_back();
        }
      } else {
        stk.push_back({c, 1});
      }
    }
    string ans;
    for (auto [c, v] : stk) {
      ans += string(v, c);
    }
    return ans;
  }
};

func removeDuplicates(s string, k int) string {
  stk := []pair{}
  for _, c := range s {
    if len(stk) > 0 && stk[len(stk)-1].c == c {
      stk[len(stk)-1].v = (stk[len(stk)-1].v + 1) % k
      if stk[len(stk)-1].v == 0 {
        stk = stk[:len(stk)-1]
      }
    } else {
      stk = append(stk, pair{c, 1})
    }
  }
  ans := []rune{}
  for _, e := range stk {
    for i := 0; i < e.v; i++ {
      ans = append(ans, e.c)
    }
  }
  return string(ans)
}

type pair struct {
  c rune
  v int
}

方法二

class Solution:
  def removeDuplicates(self, s: str, k: int) -> str:
    stk = []
    for c in s:
      if stk and stk[-1][0] == c:
        stk[-1][1] = (stk[-1][1] + 1) % k
        if stk[-1][1] == 0:
          stk.pop()
      else:
        stk.append([c, 1])
    ans = [c * v for c, v in stk]
    return "".join(ans)