1047.删除字符串中的所有相邻重复项

难度：容易

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. 1 <= S.length <= 20000
2. S 仅由小写英文字母组成。

解题思路

括号匹配是使用栈解决的经典问题。

本题要删除相邻相同元素，相对于 20.有效的括号 来说其实也是匹配问题，二者都是匹配元素，最后做消除的操作。

本题也是用栈来解决的经典题目。

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在 前一位 是不是存在一样数值的元素，那么如何记录前面遍历过的元素呢？

所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素，然后再去做对应的消除操作。

这里我使用 StringBuilder 来模拟栈：

1. 遍历输入字符串的每个字符
   1. 如果 StringBuilder 为空，直接添加当前字符（入栈）
   2. 如果当前字符与 StringBuilder 中最后一个字符相同，则删除 StringBuilder 中的最后一个字符（即移除重复字符，出栈）
   3. 如果当前字符与 StringBuilder 中最后一个字符不相同，将其添加到 StringBuilder 中（入栈）
2. 将处理后的字符串转换为 String 并返回

我的代码（使用 StringBuilder 模拟栈）

public String removeDuplicates(String s) {
    // 使用 StringBuilder 来动态构建和修改字符串
    StringBuilder sb = new StringBuilder();
    int ls = s.length();

    // 遍历输入字符串的每个字符
    for (int i = 0; i < ls; i++) {
        // 获取当前字符
        char c = s.charAt(i);
        if (sb.length() == 0) {
            sb.append(c);
        } else if (c == sb.charAt(sb.length() - 1)) {
            sb.deleteCharAt(sb.length() - 1);
        } else {
            sb.append(c);
        }
    }
    return sb.toString();
}

时间复杂度：O(n)

空间复杂度：O(n)

双指针做法

public String removeDuplicates(String s) {
    char[] ch = s.toCharArray();
    int ls = s.length();
    int fast = 0, slow = 0;

    while (fast < ls) {
        // 如果slow指针减少到-1，则重置slow为0
        if (slow == -1) {
            slow = 0;
        }

        // 遇到相同值时，后退slow指针
        if (slow > 0 && ch[fast] == ch[slow - 1]) {
            slow--;
        } else {
            ch[slow] = ch[fast]; // 覆盖slow指针的值
            slow++;
        }
        fast++;
    }

    return new String(ch, 0, slow);
}

时间复杂度：O(n)

空间复杂度：O(n)

总结

括号匹配是使用栈解决的经典问题。

拿字符串直接作为栈，省去了栈还要转为字符串的操作。