Given a string s, 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:

Input: s = "abcd", k = 2 Output: "abcd" Explanation:There's nothing to delete. 

Example 2:

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" 

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2 Output: "ps" 

Constraints:

• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s only contains lower case English letters.

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。在执行完所有删除操作后，返回最终得到的字符串。本题答案保证唯一。

• 暴力解法。每增加一个字符，就往前扫描 k 位，判断是否存在 k 个连续相同的字符。消除了 k 个相同字符后，重新组成的字符串还可能再次产出 k 位相同的字符，（类似消消乐，k 个相同的字符碰到一起就“消除”），还需要继续消除。最差情况要再次扫描一次字符串。时间复杂度 O(n^2)，空间复杂度 O(n)。
• 暴力解法的低效在于重复统计字符频次，如果每个字符的频次统计一次就好了。按照这个思路，利用 stack ，每个栈元素存 2 个值，一个是字符，一个是该字符对应的频次。有了栈顶字符频次信息，就不需要重复往前扫描了。只要栈顶字符频次到达了 k，就弹出该字符。如此反复，最终剩下的字符串为所求。时间复杂度 O(n)，空间复杂度 O(n)。

package leetcode // 解法一 stackfuncremoveDuplicates(sstring, kint) string { stack, arr:= [][2]int{}, []byte{} for_, c:=ranges { i:=int(c-'a') iflen(stack) >0&&stack[len(stack)-1][0] ==i { stack[len(stack)-1][1]++ifstack[len(stack)-1][1] ==k { stack=stack[:len(stack)-1] } } else { stack=append(stack, [2]int{i, 1}) } } for_, pair:=rangestack { c:=byte(pair[0] +'a') fori:=0; i<pair[1]; i++ { arr=append(arr, c) } } returnstring(arr) } // 解法二 暴力funcremoveDuplicates1(sstring, kint) string { arr, count, tmp:= []rune{}, 0, '#'for_, v:=ranges { arr=append(arr, v) forlen(arr) >0 { count=0tmp=arr[len(arr)-1] fori:=len(arr) -1; i>=0; i-- { ifarr[i] !=tmp { break } count++ } ifcount==k { arr=arr[:len(arr)-k] } else { break } } } returnstring(arr) }