[LeetCode] 1209. Remove All Adjacent Duplicates in String II

[grandyang]

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Constraints:

• 1 <= s.length <= 105
• 2 <= k <= 104
• s only contains lower case English letters.

这道题是之前那道 Remove All Adjacent Duplicates In String 的拓展，那道题只是让移除相邻的相同字母，而这道题让移除连续k个相同的字母，规则都一样，移除后的空位不保留，断开的位置重新连接，则有可能继续生成可以移除的连续字母。最直接暴力的解法就是多次扫描，每次都移除连续k个字母，然后剩下的字母组成新的字符串，再次进行扫描，但是这种方法现在超时了 Time Limit Exceeded，所以必须要用更加高效的解法。由于多次扫描可能会超时，所以要尽可能的在一次遍历中就完成，对于已经相邻的相同字母容易清除，断开的连续字母怎么一次处理呢？答案是在统计的过程中及时清除连续的字母，由于只能遍历一次，所以清除的操作可以采用字母覆盖的形式的，则这里可以使用双指针 Two Pointers 来操作，i指向的是清除后没有k个连续相同字母的位置，j是当前遍历原字符串的位置，这里还需要一个数组 cnt，其中 cnt[i] 表示字母 s[i] 连续出现的个数。i和j初始化均为0，开始遍历字符串s，用 s[j] 来覆盖 s[i]，然后来更新 cnt[i]，判断若i大于0，且 s[i - 1] 等于 s[i]，说明连续字母的个数增加了一个，用 cnt[i-1] + 1 来更新 cnt[i]，否则 cnt[i] 置为1。这样最终前字符串s的前i个字母就是最终移除后剩下的结果，直接返回即可，参见代码如下：

解法一：

class Solution {
public:
    string removeDuplicates(string s, int k) {
        int i = 0, n = s.size();
        vector<int> cnt(n);
        for (int j = 0; j < n; ++j, ++i) {
            s[i] = s[j];
            cnt[i] = (i > 0 && s[i - 1] == s[i]) ? cnt[i - 1] + 1 : 1;
            if (cnt[i] == k) i -= k;
        }
        return s.substr(0, i);
    }
};

我们也可以使用栈来做，这里用个数组来模拟栈，栈中放一个由字符的出现和次数和该字符组成的 pair 对儿，初始化时放个 {0, '#'} 进去，是为了防止栈为空。然后开始遍历字符串s的每个字符c，此时判断若栈顶的 pair 对儿不是字符c，则组成的新的 pair 对儿 {1, c} 压入栈中，否则将栈顶 pair 对儿的次数自增1，若此时正好等于k了，则将栈顶 pair 对儿移除，这样最终的残留部分都按顺序保留在栈中了。此时就发现用数组的好处了，因为可以从开头遍历，按顺序将剩余部分放入结果 res 中即可，参见代码如下：

解法二：

class Solution {
public:
    string removeDuplicates(string s, int k) {
        string res;
        vector<pair<int, char>> st{{0, '#'}};
        for (char c : s) {
            if (st.back().second != c) {
                st.push_back({1, c});
            } else if (++st.back().first == k) {
                st.pop_back();
            }
        }
        for (auto &a : st) {
            res.append(a.first, a.second);
        }
        return res;
    }
};

Github 同步地址:

#1209

类似题目：

Remove All Adjacent Duplicates In String

参考资料：

https://leetcode.com/problems/get-equal-substrings-within-budget/

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/discuss/392933/JavaC%2B%2BPython-Two-Pointers-and-Stack-Solution

LeetCode All in One 题目讲解汇总(持续更新中...)