Medium

题目描述

给你一个字符串 s 和一个整数 k，一个 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 个时就将其删除。

方法一：栈 + 计数 使用一个栈存储字符及其连续出现的次数。遍历字符串：

  • 如果当前字符与栈顶字符相同，则增加计数
  • 如果不同，则将新字符压入栈
  • 当某个字符的计数达到 k 时，将其从栈中删除

方法二：双指针优化 可以直接在原字符串上进行操作，使用双指针模拟栈的行为，减少空间开销。

这里推荐方法一，因为逻辑更清晰，代码更易理解。栈中存储字符和对应的计数，当计数达到 k 时立即删除，这样可以确保每次操作都是最优的。

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是字符串长度。由于每个字符最多被处理一次，所以效率很高。

代码实现

class Solution {
public:
    string removeDuplicates(string s, int k) {
        stack<pair<char, int>> st;
        
        for (char c : s) {
            if (!st.empty() && st.top().first == c) {
                st.top().second++;
                if (st.top().second == k) {
                    st.pop();
                }
            } else {
                st.push({c, 1});
            }
        }
        
        string result;
        while (!st.empty()) {
            auto [ch, count] = st.top();
            st.pop();
            result = string(count, ch) + result;
        }
        
        return result;
    }
};

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        
        for char in s:
            if stack and stack[-1][0] == char:
                stack[-1] = (char, stack[-1][1] + 1)
                if stack[-1][1] == k:
                    stack.pop()
            else:
                stack.append((char, 1))
        
        result = []
        for char, count in stack:
            result.append(char * count)
        
        return ''.join(result)

public class Solution {
    public string RemoveDuplicates(string s, int k) {
        var stack = new Stack<(char ch, int count)>();
        
        foreach (char c in s) {
            if (stack.Count > 0 && stack.Peek().ch == c) {
                var (ch, count) = stack.Pop();
                if (count + 1 == k) {
                    continue;
                } else {
                    stack.Push((ch, count + 1));
                }
            } else {
                stack.Push((c, 1));
            }
        }
        
        var result = new StringBuilder();
        var temp = new Stack<(char, int)>();
        
        while (stack.Count > 0) {
            temp.Push(stack.Pop());
        }
        
        while (temp.Count > 0) {
            var (ch, count) = temp.Pop();
            result.Append(new string(ch, count));
        }
        
        return result.ToString();
    }
}

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var removeDuplicates = function(s, k) {
    const stack = [];
    
    for (const char of s) {
        if (stack.length > 0 && stack[stack.length - 1][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 每个字符最多被处理一次
空间复杂度O(n) - 栈最多存储 n 个元素

相关题目