难度: Medium
给你一个字符串 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^52 <= k <= 10^4s 中只含有小写英文字母。运行时间: 62 ms
内存: 20.5 MB
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = [] # Stack to store characters along with their counts
for char in s:
if not stack or stack[-1][0] != char:
stack.append([char, 1])
else:
stack[-1][1] += 1
if stack[-1][1] == k:
stack.pop()
res = ''
for i, v in stack:
res += i * v
return res
此题解采用栈的数据结构来解决问题。对于每一个字符，若栈为空或栈顶元素与当前字符不同，则将此字符和计数1作为一个列表推入栈中。如果栈顶元素与当前字符相同，则增加栈顶元素的计数。当栈顶元素的计数达到k时，将其从栈中弹出，这模拟了删除k个相同字符的操作。最后，栈中剩余的元素代表了最终的字符串，其中每个元素包括字符及其剩余次数，将它们拼接起来得到最终结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = [] # 使用栈来存储字符及其出现次数
for char in s:
if not stack or stack[-1][0] != char:
stack.append([char, 1]) # 如果栈为空或栈顶字符不等于当前字符，将当前字符推入栈
else:
stack[-1][1] += 1 # 否则，增加栈顶字符的计数
if stack[-1][1] == k:
stack.pop() # 如果栈顶字符计数达到k，将其从栈中移除
res = ''
for i, v in stack:
res += i * v # 拼接最终结果字符串
return res
栈是一种后进先出（LIFO）的数据结构，它非常适合处理与最近相关的元素。在本题中，我们需要关注最近添加的字符和其出现次数，以便能够在达到重复次数k时迅速移除它们。使用栈可以让我们轻松地访问和操作这些最近的字符及其计数信息。而如果使用队列（先进先出），则需要额外的操作来访问队尾的元素，这会增加实现的复杂性。使用链表虽然可以高效地在任何位置插入或删除，但其在内存中通常不如栈或队列连续，且节点的额外指针会增加内存消耗。因此，栈在此类问题中提供了既简单又高效的解决方案。
在实现中，每次字符入栈前，都会检查栈顶元素。如果栈顶元素被移除后（因为其计数达到k），则再次检查新的栈顶元素是否与当前处理的字符相同。如果相同，我们继续增加该栈顶元素的计数。如果不同或栈为空，则将当前字符以新的元素形式推入栈中。因此，通过每次都重新检查栈顶元素，可以确保连续相同的字符被正确地计数和处理，无论它们是原本就在栈中，还是由于中间元素的移除而暴露出来。
考虑字符串 'aabbaabb' 和 k = 2 的情况。初始时，字符 'a' 入栈，计数变为1，再次 'a' 入栈，计数变为2，然后因达到k，这对'a'被移除。接下来，两个 'b' 重复上述过程，也被移除。此时，栈为空，然后再次遇到 'a' 和 'b'，重复之前的入栈和移除过程。在这种情况下，每个字符都进栈两次并被移除。这种反复进出栈的情况发生在字符的重复次数恰好与k相等，且这种模式多次出现的场景中。