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

给你一个字符串  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 中只含有小写英文字母

题目描述的很清晰了，看完题目，第一反应就是用栈，只需要一次遍历，可以在O(n)的复杂度内给出答案。

下面是基于python3的代码实现

class Solution:

def removeDuplicates(self, s: str, k: int) -> str:

# 栈顶的元素为[x, y]的列表， 其中：

# x为字符串s的迭代字符

# y为字符x连续出现的次数

stack = []

for i in s:

# 如果栈为空，则字符i首次出现，[i,1]入栈

if not stack:

stack.append([i, 1])

else:

# 如果i恰好为栈顶的字符，则出现次数加一，否则[i,1]入栈

if i == stack[-1][0]:

stack[-1][1] += 1

# 判断字符i的出现次数，如果出现k次，则直接出栈删除

if stack[-1][1] >= k:

stack.pop()

else:

stack.append([i, 1])

# 连接栈中的元素，并返回结果

res = "".join([i[0]*i[1] for i in stack])

return res