1209. 删除字符串中的所有相邻重复项 II：开心消消乐，先进先出的栈.md

题目简述：

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

题目链接：1209. 删除字符串中的所有相邻重复项 II

思路

开心消消乐就行，尽可能删除相邻的重复项。删除一段重复项后有可能产生新的连续重复项，而这天然适配栈的逻辑。

和括号匹配问题是有点相似的。

代码

算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

class Solution {
    public String removeDuplicates(String s, int k) {
        Deque<Node> stack = new ArrayDeque<>();
        
        for (int i = 0; i < s.length(); i++) {
            char cc = s.charAt(i);

            if (stack.isEmpty() || stack.peek().c != cc) {
                stack.push(new Node(cc, 1));
            } else {
                if (stack.peek().freq + 1 == k) {
                    stack.pop();
                } else {
                    stack.peek().freq++;
                }
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.append(stack.removeLast().toString());
        }
        return res.toString();
    }

    class Node {

        char c;
        int freq;
        
        Node (char c, int freq) {
            this.c = c;
            this.freq = freq;
        }

        public String toString() {
            return String.valueOf(c).repeat(freq);
        }
    }
}