1209. 删除字符串中的所有相邻重复项 II
1209. 删除字符串中的所有相邻重复项 II
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
本题答案保证唯一。
示例 1：
输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释：
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"
「提示：」
1 <= s.length <= 10^52 <= k <= 10^4s中只含有小写英文字母。
思路：
与上一题类似，也是借用栈来求解。不同的是，这里是删除相邻重复k次的项。那么可以这么做：
遍历字符串的每个字符元素，
- 如果栈为空，则直接放入栈中；
- 如果栈顶元素的首项不等于当前元素，那么意味着不重复，则将元素放入栈中；
- 如果栈顶元素的首项等于当前元素，但是栈顶元素字符串的长度小于k - 1，则依旧不构成重复的条件；因为算上当前元素加上k - 1才能达到相邻k项的要求，因此将当前元素拼接到栈顶字符串后面，等待后续元素，如果后续元素刚好等于这个元素，就达到了消除的条件；
- 如果栈顶元素的首项等于当前元素，且满足消除条件，则消除栈顶元素。
需要注意的是，每次遍历都是将栈顶元素弹出进行判断。
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var removeDuplicates = function(s, k) {
let stack = [];
let idx = 0;
while (idx < s.length) {
const prev = stack.pop();
if (!prev) { // 栈为空，直接添加
stack.push(s[idx++]);
continue;
}
if (prev[0] !== s[idx]) stack.push(prev, s[idx++]); // 不是重复元素，继续往栈里添加
else if (prev.length < k - 1) stack.push(prev + s[idx++]); // 是重复元素，但没达到消除条件
else idx++; // 满足条件，消除
}
return stack.join(''); // 拼接为字符串，并返回
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-04-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
