题目描述
给你一个字符串 s
,k 倍重复项删除操作 将会从 s
中选择 k
个相邻且相等的字母,并删除它们,使被删去的字符串的左侧和右侧连在一起。
你需要对 s
重复进行无限次这样的删除操作,直到无法继续为止。
在执行完所有删除操作后,返回最终得到的字符串。
本题答案保证唯一。
样例
输入:s = "abcd", k = 2
输出:"abcd"
解释:没有要删除的内容。
输入:s = "deeedbbcccbdaa", k = 3
输出:"aa"
解释:
先删除 "eee" 和 "ccc",得到 "ddbbbdaa"
再删除 "bbb",得到 "dddaa"
最后删除 "ddd",得到 "aa"
输入:s = "pbbcggttciiippooaais", k = 2
输出:"ps"
限制
1 <= s.length <= 10^5
2 <= k <= 10^4
s
中只含有小写英文字母。
算法
(动态维护数组信息) O(n)
- 我们对每个位置动态维护当前重复字母的长度
len
以及上一个没被删除字母的位置last
。 - 遍历过程中,用
cur_last
记录上一个没被删除字母的位置。 - 如果当前字母和上一个字母不一致,则当前位置的上一个位置记为
cur_last
,cur_last
修改为i
,当前位置的重复长度记为1
。 - 如果当前字母和上一个字母一致,则当前位置的上一个位置记为
cur_last
,当前位置的重复长度记为len[cur_last] + 1
,cur_last
修改为i
。然后,如果当前位置的重复长度为k
,则进行删除操作,我们顺着last
数组往回找,直到找到-1
或者和当前字母不相等位置,将过程中所有的位置的长度记为-1
。 - 最后拼接长度不是
-1
的位置。 - 本质上是维护了一个 stack,但不用真正表示出来。
时间复杂度
- 每个位置最多遍历两次,故时间复杂度为 O(n)。
空间复杂度
- 需要额外的数组记录每个位置的信息,故空间复杂度为 O(n)。
C++ 代码
class Solution {
public:
string removeDuplicates(string s, int k) {
int n = s.length();
vector<int> len(n), last(n);
int cur_last = -1;
for (int i = 0; i < n; i++) {
if (cur_last == -1 || s[i] != s[cur_last]) {
last[i] = cur_last;
cur_last = i;
len[i] = 1;
} else if (s[i] == s[cur_last]) {
last[i] = cur_last;
len[i] = len[cur_last] + 1;
cur_last = i;
if (len[i] == k) {
while (cur_last != -1 && s[cur_last] == s[i]) {
len[cur_last] = -1;
cur_last = last[cur_last];
}
}
}
}
string ans;
for (int i = 0; i < n; i++)
if (len[i] != -1)
ans += s[i];
return ans;
}
};
直接统计连续相同字符似乎更清晰一些:
class Solution { public: string removeDuplicates(string s, int k) { string stk("#"); stack<int> cnt; cnt.push(1); for(int i = 0 ; i < s.size() ; i++) { if(s[i] == stk.back()) cnt.push(cnt.top()+1); else cnt.push(1); stk += s[i]; if(cnt.top() >= k) { for(int j = 0 ; j < k ; j++) { stk.pop_back(); cnt.pop(); } } } return stk.substr(1); } };
Excellent!
比赛的时候没时间仔细考虑优化,有一点思路就直接写了