跳转至

1209. 删除字符串中的所有相邻重复项 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 中只含有小写英文字母。

解法

方法一：栈

思考

反复扫描删除连续 \(k\) 个相同字符，\(n \le 10^5\) 时最坏会多次重扫。删除具有局部性：只有相邻的相同字符会合并，且删除后两侧可能再相遇。

栈按从左到右的顺序保存尚未消除的字符及其连续次数。当前字符与栈顶相同则累加；次数达到 \(k\) 则整段弹出，相当于一次消除。

为此栈中存 \((字符, 次数)\)，入栈时对 \(k\) 取模以便刚好满 \(k\) 时弹出。一遍扫描后栈内剩余即最终串。

我们可以遍历字符串 \(s\)，维护一个栈，栈中存储的是字符和该字符出现的次数。当遍历到字符 \(c\) 时，如果栈顶元素的字符和 \(c\) 相同，则将栈顶元素的次数加一，否则将字符 \(c\) 和次数 \(1\) 入栈。当栈顶元素的次数等于 \(k\) 时，将栈顶元素出栈。

遍历完字符串 \(s\) 后，栈中存储的就是最终结果。我们可以将栈中的元素依次弹出，拼接成字符串即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为字符串 \(s\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stk = []
        for c in s:
            if stk and stk[-1][0] == c:
                stk[-1][1] = (stk[-1][1] + 1) % k
                if stk[-1][1] == 0:
                    stk.pop()
            else:
                stk.append([c, 1])
        ans = [c * v for c, v in stk]
        return "".join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public String removeDuplicates(String s, int k) {
        Deque<int[]> stk = new ArrayDeque<>();
        for (int i = 0; i < s.length(); ++i) {
            int j = s.charAt(i) - 'a';
            if (!stk.isEmpty() && stk.peek()[0] == j) {
                stk.peek()[1] = (stk.peek()[1] + 1) % k;
                if (stk.peek()[1] == 0) {
                    stk.pop();
                }
            } else {
                stk.push(new int[] {j, 1});
            }
        }
        StringBuilder ans = new StringBuilder();
        for (var e : stk) {
            char c = (char) (e[0] + 'a');
            for (int i = 0; i < e[1]; ++i) {
                ans.append(c);
            }
        }
        ans.reverse();
        return ans.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> stk;
        for (char& c : s) {
            if (stk.size() && stk.back().first == c) {
                stk.back().second = (stk.back().second + 1) % k;
                if (stk.back().second == 0) {
                    stk.pop_back();
                }
            } else {
                stk.push_back({c, 1});
            }
        }
        string ans;
        for (auto [c, v] : stk) {
            ans += string(v, c);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func removeDuplicates(s string, k int) string {
    stk := []pair{}
    for _, c := range s {
        if len(stk) > 0 && stk[len(stk)-1].c == c {
            stk[len(stk)-1].v = (stk[len(stk)-1].v + 1) % k
            if stk[len(stk)-1].v == 0 {
                stk = stk[:len(stk)-1]
            }
        } else {
            stk = append(stk, pair{c, 1})
        }
    }
    ans := []rune{}
    for _, e := range stk {
        for i := 0; i < e.v; i++ {
            ans = append(ans, e.c)
        }
    }
    return string(ans)
}

type pair struct {
    c rune
    v int
}

评论