[Swift]LeetCode1209. 删除字符串中的所有相邻重复项 II | Remove All Adjacent Duplicates in String II
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given a string s, a kduplicate 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^52 <= k <= 10^4sonly contains lower case English letters.
给你一个字符串 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中只含有小写英文字母。
Runtime: 84 ms
Memory Usage: 21.5 MB
1 class Solution {
2 func removeDuplicates(_ s: String, _ k: Int) -> String {
3 var st:[Character] = [Character]()
4 var cnt:[Int] = [Int]()
5 for c in s
6 {
7 if st.count > 0 && st.last! == c
8 {
9 cnt[cnt.count - 1] += 1
10 }
11 else
12 {
13 st.append(c)
14 cnt.append(1)
15 }
16 while(st.count > 0 && cnt.last! == k)
17 {
18 st.removeLast()
19 cnt.removeLast()
20 }
21 }
22 var ret:String = String()
23 for i in 0..<st.count
24 {
25 ret += String(repeating:st[i],count:cnt[i])
26 }
27 return ret
28 }
29 } 32ms
1 class Solution {
2 func removeDuplicates(_ s: String, _ k: Int) -> String {
3
4 if k <= 1 {
5 return ""
6 }
7 if s.count < 1 {
8 return s
9 }
10 var chars = Array(s)
11
12 func remove(_ chars: inout [Character]) {
13 if chars.count < k {
14 return
15 }
16
17 var ct = 1
18 var idx = -1
19 for i in 1..<chars.count {
20 if chars[i] == chars[i-1] {
21 ct += 1
22 } else {
23 ct = 1
24 }
25
26 if ct >= k {
27 idx = i
28 break
29 }
30 }
31
32 if idx != -1 {
33 chars.removeSubrange(idx-k+1...idx)
34 // print(chars)
35 remove(&chars)
36 }
37 }
38 remove(&chars)
39 return String(chars)
40 }
41 }36ms
1 class Solution {
2 func removeDuplicates(_ s: String, _ k: Int) -> String {
3 var stack = [Character]()
4 var count = 1
5 for c in s {
6 stack.append(c)
7
8 if stack.count > 1 {
9 if stack[stack.count - 1] == stack[stack.count - 2] {
10 count += 1
11 if count == k {
12 stack.removeLast(k)
13 if !stack.isEmpty {
14 count = 0
15 var i = stack.count - 1
16 let last = stack[i]
17 while i >= 0, stack[i] == last {
18 count += 1
19 i -= 1
20 }
21 } else {
22 count = 1
23 }
24 }
25 } else {
26 count = 1
27 }
28 }
29 }
30
31 return String(stack)
32 }
33 }40ms
1 class Solution {
2 func removeDuplicates(_ s: String, _ k: Int) -> String {
3
4 guard k > 1 else { return "" }
5 var stack = Array(s)
6
7 var arr = [Int](repeating: 0, count: s.count)
8
9 var end = 0
10 for c in s {
11 stack[end] = c
12 if end == 0 {
13 arr[end] = 1
14 } else if stack[end] == stack[end-1] {
15 arr[end] = arr[end-1] + 1
16 } else {
17 arr[end] = 1
18 }
19
20 while end + 1 >= k && arr[end] == k {
21 end = end + 1 - k - 1
22 }
23 end += 1
24 }
25 return String(stack[0..<end])
26 }
27 }56ms
1 class Solution {
2 func removeDuplicates(_ s: String, _ k: Int) -> String {
3 var stack: [(character: Character, count: Int)] = []
4
5 for c in s {
6 guard let last = stack.last, last.character == c else {
7 stack.append((c, 1))
8 continue
9 }
10
11 if last.count == k - 1 {
12 _ = stack.removeLast()
13 } else {
14 stack[stack.count - 1] = (c, last.count + 1)
15 }
16 }
17
18 var ans: String = ""
19 for value in stack {
20 ans.append(contentsOf: String(repeating: value.character, count: value.count))
21 }
22
23 return ans
24 }
25 }