面试真题：删除字符串中出现次数 >= 2 次的相邻字符

[sisterAn]

输入："abbbaca"
输出："ca"
解释："abbbaca" => "aaca"=>"ca"

[thxiami]

时间复杂度: O(n), n 为字符的个数
空间复杂度: O(n), 栈所用的空间

/**
 * 删除字符串中出现次数 >= 2 次的相邻字符
 * @param{string}s
 */
function removeDuplicate(s) {
 const stack = [] // Space: O(n)
 let top
 let next
 let i = 0
 while (i < s.length) { // Time: O(n)
 top = stack[stack.length - 1]
 next = s[i]
 if (next === top) {
 // 字符串中出现了相邻字符
 // 1. 移除栈顶字符
 // 2. 移动指针, 指向下一个不同的字符
 stack.pop()
 while (s[i] === top) i += 1
 } else {
 stack.push(next)
 i += 1
 }
 }

 return stack.join('') // Time: O(n)
}

[13001920223]

在昨天瓶子酱的基础上增加了判断，如果下一个还是相同字符串，继续累加
没有测试用例，有问题欢迎指出

var removeDuplicates = function(s, k) {
 let stock = []
 for (let i = 0; i < s.length; i++) {
 let prev = stock.pop()
 if (!prev || prev[0] !== s[i]) { // 取第一个字符比较
 stock.push(prev)
 stock.push(s[i])
 } else if(prev.length < k - 1 || prev[0] === s[i+1]) { // 如果长度达不到删除数量 或者与下一个字符相同则继续累加
 stock.push(prev+s[i]) // 相同字符拼接在一起
 }
 }
 return stock.join('')
};

[sisterAn]

时间复杂度: O(n), n 为字符的个数
空间复杂度: O(n), 栈所用的空间

/**
 * 删除字符串中出现次数 >= 2 次的相邻字符
 * @param{string}s
 */
function removeDuplicate(s) {
 const stack = [] // Space: O(n)
 let top
 let next
 let i = 0
 while (i < s.length) { // Time: O(n)
 top = stack[stack.length - 1]
 next = s[i]
 if (next === top) {
 // 字符串中出现了相邻字符
 // 1. 移除栈顶字符
 // 2. 移动指针, 指向下一个不同的字符
 stack.pop()
 while (s[i] === top) i += 1
 } else {
 stack.push(next)
 i += 1
 }
 }

 return stack.join('') // Time: O(n)
}

👍👍👍

[zhaojinzhao]

var arr = 'abbbaca'.split('');
var startIndex = 0;
while(startIndex < arr.length){
var endIndex = startIndex;
while(arr[endIndex + 1] === arr[startIndex]){
endIndex++;
}
if (startIndex !== endIndex){
arr.splice(startIndex, endIndex - startIndex + 1);
startIndex = Math.max(0, startIndex - 1);
} else{
startIndex++;
}
}
arr.join('');

[HanTianPeng]

解题思路：保证相同字符串始终作为栈的一个元素进行存储。
时间复杂度:O(n), 空间复杂度O(n)

function removeDuplicateMoreTwo(s) {
 let stack1 = new Stack();
 for(let i=0; i<s.length; i++) {
 let popValue = stack1.pop(),
 iValue = s[i];
 
 if(popValue === null) {
 stack1.push(iValue);
 }else if(popValue[0] !== iValue) {
 if(popValue.length >= 2) {
 let secondPopValue = stack1.pop();
 if(secondPopValue === iValue){
 stack1.push(secondPopValue + iValue);
 }else{
 stack1.push(secondPopValue);
 stack1.push(iValue);
 }
 }else{
 stack1.push(popValue);
 stack1.push(iValue);
 }
 }else if(popValue[0] === iValue) {
 stack1.push(popValue + iValue);
 }
 }
 return stack1.dataStore.join('');
}

[iconWave]

const removeDuplicates = (str) =>{
 if (str.length === 0) return ''
 let newStr = str.slice(0)
 for(let i = 0; i < newStr.length; i++){
 if(newStr[i] === newStr[i + 1]){
 newStr = newStr.replace(/(\w)\1+/g, '')
 i === 0 ? (i = i - 1) : (i = i - 2)
 }
 }
 return newStr
}

[supershutong]

这个和letcode 1209有什么区别吗，从瓶子给的示例看，这完全一样啊

[haydenull]

这个和letcode 1209有什么区别吗，从瓶子给的示例看，这完全一样啊

@supershutong

可以比较下输入字符串为 "aaa" 时的结果，本题返回 "" ，之前的那题返回 "a"

[qianlongo]

正则 + 递归

var removeDuplicates = function(s, k = 2) {
 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)
 }
};

[XW666]

const removeDup = (s) =>{

let stack = []

for (let i = 0; i < s.length; i++){
 let prev = stack.pop()
 if (prev !== s[i]){
 stack.push(prev)
 stack.push(s[i])
 } else if (prev === s[i + 1]){
 stack.push(s[i + 1])
 }
}
return stack.join('')

}
removeDup('abbbaca')

[tomorrowIsNewDay]

function ans(str){
// 正则+递归
const reg = /(\w)\1+/g
if(!reg.test(str)) return str
return ans(str.replace(reg, ''))
}

[JohnApache]

和 删除 k 位数一样的方案, 使用 带有 count 字段的对象 作为栈节点, 方便 pop的操作，但是不同的是 边界条件的判断， 因为是 ，不知道会重复多少次，所以删除节点放到 push 下一个不同字符的节点前, 一起删除，

还有需要注意的边界条件有两点

• 删除节点后下一个值可能会和上一个值重复，这里需要再做一次单独判断，给重复的节点 count 累加，用于下轮判断的时候删除
• 当字符扫描到最后一位的时候，由于我们是在 push 前 pop, 做了前面的一点的判断只会给节点的 count 累加值，因为没有下一轮循环了，所以需要在这个特殊的位置，做一次单独的 pop

interface StackNode {
 value: string;
 count: number;
}
const removeDuplicates = (source: string) => {
 if (source.length <= 1) 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;
 }
 let lastStackNode = stack[stack.length - 1];
 if (lastStackNode.value !== source[i]) {
 // 先判断栈顶节点是否超过2个了，超过就删除
 // 删除节点放在这里是因为我们不知道会有多少个重复字符，可以等到字符变了的时候，再判断，这时候可以一起删除，减少pop次数
 if (lastStackNode.count >= 2) {
 stack.pop();
 lastStackNode = stack[stack.length - 1];
 }
 if (lastStackNode && lastStackNode.value === source[i]) {
 if (i === source.length - 1) {
 // 最后一位的时候直接pop ,
 stack.pop();
 } else {
 lastStackNode.count++;
 }
 continue;
 }

 stack.push({ value: char, count: 1 });
 continue;
 }
 lastStackNode.count++;
 }
 return stack.reduce((prev, cur) => prev + cur.value.repeat(cur.count), '');
};