1209. Remove All Adjacent Duplicates in String II

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation