栈｜ Leetcode 1209

Leetcode 分类刷题 —— 栈（Stack）

1、题目描述：

Leetcode 1209. Remove All Adjacent Duplicates in String II 删除字符串中的所有相邻重复项 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.

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。本题答案保证唯一。

2、解题思路：

可以使用栈来解决这个问题，栈中的每个元素是个包含两个元素的Pair，第一个元素是字符，第二个元素是该字符到当前位置为止已经连续出现过的次数。
具体思路是遍历字符串s，对于每个字符，将其与栈顶元素比较：
如果相同，则将该字符出现次数加1；
如果不同，则将该字符及其出现次数1入栈；
如果出现次数达到了k，则弹出栈顶元素。

3、代码

import javafx.util.Pair;

import java.util.ArrayDeque;
import java.util.Deque;
 
public class Solution {
    public String removeDuplicates(String s, int k) {
        // 创建一个栈来存储字符和它们的出现次数
        Deque<Pair<Character, Integer>> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            // 如果栈不为空且栈顶元素与当前字符相同，则将它们的计数器相加
            if (!stack.isEmpty() && stack.peek().getKey() == c) {
                int count = stack.pop().getValue() + 1;

                // 如果计数器等于k，则不将字符和计数器重新入栈
                if (count != k) {
                    stack.push(new Pair<>(c, count));
                }
            } else {
                // 如果栈为空或者栈顶元素与当前字符不同，则将当前字符和计数器入栈
                stack.push(new Pair<>(c, 1));
            }
        }

        // 创建一个StringBuilder对象用于构建最终字符串
        StringBuilder result = new StringBuilder();

        // 将栈中的字符和它们的出现次数转换为字符串
        while (!stack.isEmpty()) {
            Pair<Character, Integer> top = stack.pop();
            char c = top.getKey();
            int count = top.getValue();

            // 将字符和它们的出现次数添加到StringBuilder对象中
            for (int i = 0; i < count; i++) {
                result.append(c);
            }
        }

        // 反转StringBuilder对象并将其转换为String对象
        return result.reverse().toString();
    }
}