leetcode1209：删除字符串中的所有相邻重复项 II

[sisterAn]

给你一个字符串 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^5
• 2 <= k <= 10^4
• s 中只含有小写英文字母。

附赠 leetcode 地址：leetcode

[7777sea]

var removeDuplicates = function(s, k) {
 let stack = [];
 for(let _s of s){
 const last = stack.pop();
 if(!last || last[0] !== _s){
 stack.push(last)
 stack.push(_s)
 }else if(last.length < k-1){
 stack.push(last + _s)
 }
 }

 return stack.join('')
};

[huangd-d]

function delStr(s = '', k = 2) {
 if (typeof s !== 'string' || k < 2) {
 return;
 }
 let c = new RegExp(`(.)\\1{${k-1}}`, 'g');
 while (s !== s.replace(c, '')) {
 s = s.replace(c, '');
 }

 return s;
 }

[AiKunnnnn]

原理跟昨天的题是一样的，不过昨天的题是一次入栈一个，今天是k个。那我们就让它每次入栈 k-1 个，站头的 k-1 个元素的第一个如果与当前准备入栈的元素相同，则代表k个元素是一样的，则无需入栈。

var removeDuplicates = function(s, k) {
 let stack = [];
 for(let c of s){
 const prev = stack.pop();
 if(!prev || prev[0] !== c){
 stack.push(prev)
 stack.push(c)
 }else if(prev.length < k-1){
 stack.push(prev + c)
 }
 }
 return stack.join('')
};

[sisterAn]

解答：利用栈

解题思想： 遍历字符串依次入栈，入栈时，判断当前元素与栈头元素是否一致，如果不一致则入栈，如果一致，判断栈头字符是否长度为 k - 1 ，如果为 k-1 ，即加入该字符时，满足连续相同字符 k 个，此时，需要栈头出栈，当前字符不进栈，如果小于 k-1 ，则取出栈头字符，加上当前字符，重新入栈

代码实现：

const removeDuplicates = function(s, k) {
 let stack = []
 for(let c of s) {
 let prev = stack.pop()
 if(!prev || prev[0] !== c) {
 stack.push(prev)
 stack.push(c)
 } else if(prev.length < k-1) {
 stack.push(prev+c)
 }
 }
 return stack.join('')
};

时间复杂度：O(n)

空间复杂度：O(n)

leetcode

[twinkle77]

暴力来一波

var removeDuplicates = function(s, k) {
 function findRepeatPos (s, k) {
 for (let i = 0; i < s.length - k + 1; i++) {
 let flag = true
 for (let j = i; j < i + k - 1; j++) {
 if (s[j] !== s[j + 1]) {
 flag = false
 break
 }
 }
 if (flag === true) {
 return [i, i + k - 1]
 }
 }
 return [-1]
 }

 while (true) {
 let [start, end] = findRepeatPos(s, k)
 console.log(start, end)
 if (start === -1) {
 return s
 } else {
 s = s.slice(0, start) + s.slice(end + 1)
 }
 }
 return s
};

[sisterAn]

function delStr(s = '', k = 2) {
 if (typeof s !== 'string' || k < 2) {
 return;
 }
 let c = new RegExp(`(.)\\1{${k-1}}`, 'g');
 while (s !== s.replace(c, '')) {
 s = s.replace(c, '');
 }

 return s;
 }

这种做法可以，但是它采用循环匹配替换，花费时间较长，需要考虑一下时间复杂度问题

[zhaojinzhao]

var arr = 'pbbcggttciiippooaais'.split(''), k = 2;
var startIndex = 0;
while(startIndex < arr.length) {
var num = 1;
while(arr[startIndex + num] === arr[startIndex] && num < k) {
num++;
}
if (num === k) {
arr.splice(startIndex, num);
startIndex = Math.max(0, startIndex - k + 1);
} else {
startIndex++;
}
}

[HanTianPeng]

采用两个栈来进行:
function removeDuplicateK(s, k) {
 if(k <= 0) {
 return s;
 } 
 let stack1 = new Stack();
 for(let i=0; i<s.length; i++) {
 let iValue = s[i]
 stack2 = new Stack(),
 j = 0,
 isValid = true;
 while(j < k-1) {
 let popValue = stack1.pop();
 if(popValue !== null){
 stack2.push(popValue);
 }
 if(popValue === null || popValue !== iValue) {
 isValid = false;
 break;
 }
 j += 1;
 }
 if(!isValid) {
 while(stack2.length > 0) {
 stack1.push(stack2.pop());
 }
 stack1.push(iValue);
 }
 }
 return stack1.dataStore.join('');
}

[qianlongo]

正则 + 递归

var removeDuplicates = function(s, k) {
 if (s.length < k) {
 return s
 }

 const repeatLenStrRe = new RegExp(`(.)\\1{${ k - 1 }}`, 'g')
 const replaceStr = s.replace(repeatLenStrRe, '')
 // 说明没有需要再匹配的了
 if (replaceStr === s) {
 return replaceStr
 } else {
 return removeDuplicates(replaceStr, k)
 }
};

[Forever17s]

大家来评评理。对于以下测试用例，我输出“is”有什么不对吗

"pbbcggttciiippooaais"
2

预期结果
"ps"

下面是我的代码

var removeDuplicates = function(s, k) {
 for (let left = 0; i < s.length - k + 1; left++) {
 let right = i;
 while (s[right + 1] == s[left]) {
 right = right + 1;
 }

 const gap = right - left + 1;
 if (gap >= k) {
 s = s.substr(0, i) + s.substr(i + gap, s.length)
 left = -1
 }
 }
 return s
};

执行过程输出

pbbcggttciiippooaais --> pcggttciiippooaais
pcggttciiippooaais --> pcttciiippooaais
pcttciiippooaais --> pcciiippooaais
pcciiippooaais --> piiippooaais
piiippooaais --> pppooaais
pppooaais --> ooaais
ooaais --> aais
aais --> is

[JohnApache]

和删除相邻重复项是同一个类型，利用栈来存储扫描过的字符，不一样的是该题支持 k 个，这个理论上可以按照上一题一样的原则，直接推栈就好了，但是出栈的时候，考虑到 假如 k 值很大，会做很多重复性的 pop 工作，所以我这里 将 栈的节点从单纯存储读取的字符， 改为 一个 对象，对象保存了读取的字符，和已经读取的字符数量，这样每次 pop 只需要一次即可完成任务

interface StackNode {
 value: string;
 count: number;
}
const removeDuplicates = (source: string, k: number) => {
 if (source.length <= 0 || k <= 0 || source.length < k) return source;
 const stack: StackNode[] = [];
 for (let i = 0; i < source.length; i++) {
 const char = source[i];
 if (stack.length <= 0) {
 stack.push({ value: char, count: 1 });
 continue;
 }
 const lastStackNode = stack[stack.length - 1];
 if (lastStackNode.value !== source[i]) {
 stack.push({ value: char, count: 1 });
 continue;
 }
 if (lastStackNode.count === (k - 1)) {
 stack.pop();
 } else {
 lastStackNode.count++;
 }
 }
 return stack.reduce((prev, cur) => prev + cur.value.repeat(cur.count), '');
};