一、问题描述

题目来源于 LeetCode 上的 1047. 删除字符串中的所有相邻重复项。 给你一个字符串 s，请你删除字符串中所有相邻重复项。

示例 1：

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

提示：

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

二、方案一：使用栈

1、思路

我们可以使用栈来解决这个问题。遍历字符串 s，对于每个字符，如果栈不为空且栈顶元素与当前字符相同，则弹出栈顶元素，表示删除了一对相邻重复项。否则，将当前字符入栈。遍历结束后，栈中剩余的字符即为删除所有相邻重复项后的结果。

2、代码实现

func removeDuplicates(s string) string {
    stack := []rune{}
    for _, ch := range s {
        if len(stack) > 0 && stack[len(stack)-1] == ch {
            // 如果栈不为空且栈顶元素与当前字符相同，则弹出栈顶元素
            stack = stack[:len(stack)-1]
        } else {
            // 否则，将当前字符入栈
            stack = append(stack, ch)
        }
    }
    return string(stack)
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们只需要遍历字符串一次，对于每个字符，要么入栈，要么与栈顶元素比较后出栈，时间复杂度是 O(1)。
• 空间复杂度：O(n)，我们需要一个栈来存储字符，最坏情况下，字符串中没有相邻重复项，栈中需要存储所有字符。

三、方案二：使用双指针

1、思路

我们可以使用双指针技巧，一个指针 i 用于遍历字符串，另一个指针 j 用于指向下一个待插入的位置。当 i 遍历到一个字符时，如果 j 指向的字符与 i 指向的字符相同，则 j 向前移动一位，表示删除了一对相邻重复项。否则，将 i 指向的字符复制到 j 指向的位置，并将 j 向前移动一位。遍历结束后，j 指向的位置即为删除所有相邻重复项后的结果。

2、代码实现

func removeDuplicates(s string) string {
    // 将字符串转换为字符数组，方便操作
    chars := []rune(s)
    j := 0
    for i := 0; i < len(chars); i++ {
        if j > 0 && chars[j-1] == chars[i] {
            // 如果 j 指向的字符与 i 指向的字符相同，则 j 向前移动一位
            j--
        } else {
            // 否则，将 i 指向的字符复制到 j 指向的位置，并将 j 向前移动一位
            chars[j] = chars[i]
            j++
        }
    }
    // 返回删除所有相邻重复项后的结果
    return string(chars[:j])
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们只需要遍历字符串一次，对于每个字符，要么与 j 指向的字符比较后删除，要么复制到 j 指向的位置，时间复杂度是 O(1)。
• 空间复杂度：O(1)，我们只需要常数级别的额外空间来存储字符数组和两个指针。

四、总结

方案	时间复杂度	空间复杂度
使用栈	O(n)	O(n)
使用双指针	O(n)	O(1)

两种方案都能解决问题，但使用双指针的方案空间复杂度更低，更加优化。