题目描述

[EN | CN]

给你一个字符串 s,「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母,并删除它们,使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作,直到无法继续为止。

在执行完所有删除操作后,返回最终得到的字符串。

本题答案保证唯一。

示例 1:

1
2
3
输入:s = "abcd", k = 2
输出:"abcd"
解释:没有要删除的内容。

示例 2:

1
2
3
4
5
6
输入:s = "deeedbbcccbdaa", k = 3
输出:"aa"
解释:
先删除 "eee" 和 "ccc",得到 "ddbbbdaa"
再删除 "bbb",得到 "dddaa"
最后删除 "ddd",得到 "aa"

示例 3:

1
2
输入:s = "pbbcggttciiippooaais", k = 2
输出:"ps"

提示:

  • 1 <= s.length <= 10^5
  • 2 <= k <= 10^4
  • s 中只含有小写英文字母。

解法 1:栈

跟《LeetCode 1047. 删除字符串中的所有相邻重复项 ⌨️》的做法类似,我们维护一个栈来表示当前的最后字符,不过这里栈元素我们不是只放这个字母本身,而是放 这个字母和它对应的出现次数。当我们在遍历字符串的时候,对于当前遍历到的字符,

  • 若它与栈顶字母不同,则将该字符压入栈顶。
  • 若它与栈顶字母相同,则栈顶元素的计数加一;此时若计数等于 k,则弹出该字符。

最后利用这个剩下的栈恢复字符串即可。

假设字符串长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,保存结果。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        for char in s:
            if stack and stack[-1][0] == char:
                if stack[-1][1] == k - 1:
                    stack.pop()
                else:
                    stack[-1][1] += 1
            else:
                stack.append([char, 1])

        ret = ''
        for char, num in stack:
            ret += char * num

        return ret
  • 执行用时:92 ms,在所有 Python3 提交中击败了 72.76% 的用户。
  • 内存消耗:15 MB,在所有 Python3 提交中击败了 9.52% 的用户。

解法 2:正则表达式

跟《LeetCode 1047. 删除字符串中的所有相邻重复项 ⌨️》的做法类似,其正则表达式为 ([a-zA-Z])\1{%d},注意这里的 %d 要代入 k - 1 的值。

正则匹配,肯定慢的啦。

实现与结果如下:

1
2
3
4
5
6
7
import re
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        s, last_s = s, ''
        while s != last_s:
            s, last_s = re.sub(r'([a-zA-Z])\1{%d}' % (k - 1), '', s), s
        return s
  • 执行用时:4944 ms,在所有 Python3 提交中击败了 5.32% 的用户。
  • 内存消耗:15 MB,在所有 Python3 提交中击败了 9.52% 的用户。