LeetCode——删除字符串中的所有相邻重复项 II

Q：给你一个字符串 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"

A：

1. 暴力解：

public String removeDuplicates(String s, int k) {
        while (s.length() >= k) {
            boolean flag = true;
            StringBuilder sub = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                if (i + k <= s.length()) {
                    int count = 1;
                    int curr = s.charAt(i);
                    for (int j = i + 1; j < i + k; j++) {
                        if (curr == s.charAt(j))
                            count++;
                        else
                            break;
                    }
                    if (count == k) {
                        flag = false;
                        i = i + k - 1;
                        continue;
                    }
                }
                sub.append(s.charAt(i));
            }
            s = sub.toString();
            if (flag)
                break;
        }
        return s;
    }

2. 栈：我用双栈做的，实际上用Pair更方便（我傻了……完全忘了pair）

    public String removeDuplicates(String s, int k) {
        if (s.length() < k)
            return s;
        Stack<Character> stack = new Stack<>();
        Stack<Integer> stack1 = new Stack<>();
        stack.add(s.charAt(0));
        stack1.add(1);
        for (int i = 1; i < s.length(); i++) {
            if (!stack.empty() && stack.peek() == s.charAt(i)) {
                stack1.add(stack1.peek() + 1);
            } else
                stack1.add(1);
            stack.add(s.charAt(i));
            if (stack1.peek() == k) {
                for (int j = 0; j < k; j++) {
                    stack.pop();
                    stack1.pop();
                }
            }
        }
        StringBuilder res = new StringBuilder();
        while (!stack.empty()) {
            res.insert(0, stack.pop());
        }
        return res.toString();
    }