<div>
You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.
Example 1:
<pre>Input: s = "abcd", k = 2 Output: "abcd" Explanation: There's nothing to delete.</pre>
Example 2:
<pre>Input: s = "deeedbbcccbdaa", k = 3 Output: "aa" Explanation: First delete "eee" and "ccc", get "ddbbbdaa" Then delete "bbb", get "dddaa" Finally delete "ddd", get "aa"</pre>
Example 3:
<pre>Input: s = "pbbcggttciiippooaais", k = 2 Output: "ps" </pre>
Constraints:
1 <= s.length <= 10<sup>5</sup>2 <= k <= 10<sup>4</sup>sonly contains lower case English letters.
</div>
题目大意：
字符串中去除连续k次的字符
解题思路：
一开始用暴力法得到LTE。这题由于需要保持顺序，且元素之间是相等关系且类似于LeetCode 316 Remove Duplicate Letters，考虑用Stack。实现类似于BST的后序遍历，stack中同时记录次数
解题步骤：
N/A
注意事项：
- Stack中存元素和该元素的连续个数，这样避免往前重新计算连续了几次。若栈顶元素等于遍历元素且栈顶连续个数为k - 1就连续出栈。此情况此遍历元素不入栈
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def removeDuplicates(self, s: str, k: int) -> str:
stack, res = [], ''
for i in range(len(s)):
if stack and stack[-1][0] == s[i] and stack[-1][1] == k - 1:
while stack and stack[-1][0] == s[i]:
stack.pop()
else:
if stack and stack[-1][0] == s[i]:
stack.append((s[i], stack[-1][1] + 1))
else:
stack.append((s[i], 1))
while stack:
pair = stack.pop()
res += pair[0]
return res[::-1]
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
