1.题目

题目地址(1209. 删除字符串中的所有相邻重复项 II - 力扣（LeetCode）)

https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string-ii/

题目描述

给你一个字符串 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 中只含有小写英文字母。

2.题解

2.1 暴力枚举

思路

总体思路是从头开始遍历字符串，如果遇到相同用计数器计数直到：
1.遇见不同的但是总个数<k, 清空计数器，继续向后查找
2.总个数达到k个，这时候需要开始删除元素，然后我们需要重新遍历字符串

然后什么时候结束呢？
这里的思路十分巧妙，如果我们从头到尾遍历一遍字符串，但是字符串的个数没有发生变化（没有发生删除操作），说明此时已经找不到要删除的元素了，结束即可。

具体的处理过程这里两种思路：
1.设置计数器count初始值为1（表明记录第一个值），我每次检测当前的和下一个是否相等，相等则++计数器，这里计算的总个数是包括下一个在内的！！！
所以下面如果要进行删除的话，是从i+1开始删除，而不是i，删除k个元素（由于第一个元素和i+1相差k个元素，实际上k个中包含了i+1本身，所以我们实际上往回倒k-1个元素即可）
也就是s.erase(i + 1 - k + 1, k);
2.设置计数器count初始值为1，每次检测当前的和前一个是否相等，如果相等++计数器，这里计算的总个数就是包含当前个在内的总个数！！！
这里为了防止越界，单独处理一下i==0的情况，

代码1-以next为基准数

• 语言支持：C++

C++ Code:

class Solution {
public:
    string removeDuplicates(string s, int k) {
        int length = -1;
        // 循环直到字符串长度不再变化，表示没有更多的重复项可以删除
        while(length != s.length()) {
            length = s.length();
            for(int i = 0, count = 1; i < s.length() - 1; i++) {
                if(s[i] != s[i + 1]) {
                    count = 1; // 如果字符不同，计数器重置为1
                } else {
                    // 如果计数器达到k，删除这k个字符
                    if(++count == k) {
                        s.erase(i + 1 - k + 1, k);
                        break; // 删除后跳出循环，从头开始检查新的字符串
                    }
                }
            }
        }    
        return s; 
    }
};

代码2-以cur为基准数

class Solution {
public:
    string removeDuplicates(string s, int k) {
        int length = -1;
        while (length != s.size()) {
            length = s.size();
            for (int i = 0, count = 1; i < s.size(); ++i) {
                if (i == 0 || s[i] != s[i - 1]) {
                    count = 1;
                } else if (++count == k) {
                    s.erase(i - k + 1, k);
                    break;
                }
            }
        }
        return s;
    }
};

复杂度分析

• 时间复杂度：\(\mathcal{O}(n^2/k)\),其中\(n\)是字符串的长度。字符串扫描不超过\(n/k\)次。
• 空间复杂度：\(\mathcal{O}(1)\)。某些语言会创建字符串的副本，但算法只在字符串本身上操作。

2.2 记忆计数

思路

使用一个记忆数组记忆每个位置的连续数情况，每次新一个的记忆数组大小由：1.前一个记忆数组大小 和 2.当前数和前一个数是否相等 两个条件共同判断
这里注意在我们处于位置i进行删除后，要进行回退操作，这里回退k个，恰好退到删除数列首端的前一个，这个地方已经统计过记忆数组了，循环结束后i++自动变到了我们待求记忆数组的第一个数上

代码

class Solution {
public:
    string removeDuplicates(string s, int k) {
        int n = s.length();
        vector<int> count(n);
        for (int i = 0; i < n; i++) {
            if(i == 0 || s[i] != s[i-1]){
                count[i] = 1;
            }else{
                count[i] = count[i-1] + 1;
                if(count[i] == k){
                    s.erase(i - k + 1, k);
                    i = i - k; // 退到这k个数的前一个，结尾处i++, 就到了删除后新尾端的第一个
                }
            }
        }
        return s;
    }
};

复杂度分析

• 时间复杂度：\(O(n)\),其中\(n\)是字符串长度。每个字符仅被处理一次。
• 空间复杂度：\(\mathcal{O}(n)\),存储每个字符的计数器。

2.3 栈

思路

用栈代替上面的数组，遇到相同的则将栈顶元素加一，不同的则压入一个新的‘1’， 如果栈顶元素 == k， 则弹出栈， 进行字符串删除

代码

class Solution {
public:
    string removeDuplicates(string s, int k) {
        int n = s.length();
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            if(i == 0 || s[i] != s[i-1]){
                stk.push(1);
            }else if(++stk.top() == k){
                stk.pop();
                s.erase(i - k + 1, k);
                i = i - k;
            }
        }
        return s;
    }
};

复杂度分析

·时间复杂度：\(\mathcal{O}(n)\),其中\(n\)是字符串长度。每个字符只处理一次。

·空间复杂度：\(\mathcal{O}(n)\),栈空间。

2.4 栈重建

思路

我们之前都是将计数器存储在栈中，然后原地修改字符串。
如果将计数器 和 字符都存储在栈中，则不需要修改字符串，只需要根据栈中结果重建字符串即可。

代码

class Solution {
public:
    string removeDuplicates(string s, int k) {
        int length = -1;
        int n = s.length();
        vector<pair<int, char>> count;
        for (int i = 0; i < s.length(); ++i) {
            if(count.empty() || s[i] != count.back().second){
                count.emplace_back(1, s[i]);
            }else if(++count.back().first == k){
                count.pop_back();
            }
        }

        s = "";
        for(int i = 0; i < count.size(); i++){
            s += string(count[i].first, count[i].second);
        }

        return s;
    }
};

复杂度分析

·时间复杂度：\(\mathcal{O}(n)\),其中\(n\)是字符串长度。每个字符只处理一次。

·空间复杂度：\(\mathcal{O}(n)\),栈空间。

2.5 双指针

思路

这里对于字符串裁剪操作使用双指针又进行了一次优化
关键点在s[j] = s[i];和j -= k;上
1.如果没有发生删除，s[j] = s[i];没有任何影响
2.如果发生删除，j -= k;进行回退操作，接下来j和i是有一个位置差的，后面的s[i]就会覆盖掉前面的[j]完成变相删除操作

代码

string removeDuplicates(string s, int k) {
    auto j = 0;
    stack<int> counts;
    for (auto i = 0; i < s.size(); ++i, ++j) {
        s[j] = s[i];
        if (j == 0 || s[j] != s[j - 1]) {
            counts.push(1);
        } else if (++counts.top() == k) {
            counts.pop();
            j -= k;
        }
    }
    return s.substr(0, j);
}

复杂度分析

·时间复杂度：\(\mathcal{O}(n)\),其中\(n\)是字符串长度。每个字符只处理一次。

·空间复杂度：\(\mathcal{O}(n)\),栈空间。