给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

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

提示：

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

    题解

    这道题超级简单，用栈即可解决。遍历字符串每一个元素，如果它和栈顶元素一致，说明是相邻的重复项，栈pop即可，如果不是加入栈中，遍历完成后，栈里面的元素就是最后的结果。

    Python

    1. class Solution:
    2.   def removeDuplicates(self, S: str) -> str:
    3.       stk = list()
    4.       for ch in S:
    5.           if stk and stk[-1] == ch:
    6.               stk.pop()
    7.           else:
    8.               stk.append(ch)
    9.       return "".join(stk)

    JavaScript

    ```javascript /**
    • @param {string} S
    • @return {string} */ var removeDuplicates = function(S) { let temp = [] for(let i of S){
      1. let l = temp.length
      2. if (temp && temp[l-1] === i){
      3.     temp.pop()
      4. } else{
      5.     temp.push(i)
      6. }
      } return temp.join(‘’)

}; ```

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串的长度。只需要遍历该字符串一次。
  • 空间复杂度：O(n) 或 O(1)，取决于使用的语言提供的字符串类是否提供了类似「入栈」和「出栈」的接口。注意返回值不计入空间复杂度。