一、题目内容 简单

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

示例1：

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

提示：

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

二、解题思路

按照正常思路，我们遍历字符串，拿到字符时，和上一个字符相比较，相同则两个都去掉，不同则留下字符。
这个思路，可以让我们想到栈，从栈顶上拿刚放进去的元素。不符合，把栈顶 pop 出去。

三、具体代码

  1. /**
  2.  * @param {string} s
  3.  * @return {string}
  4.  */
  5. var removeDuplicates = function (s) {
  6.   const stack = [];
  7.   for (let i = 0; i < s.length; i++) {
  8.     if (!stack[0]) stack[0] = s[i];
  9.     else {
  10.       const pre = stack[stack.length - 1];
  11.       if (pre === s[i]) stack.pop();
  12.       else {
  13.         stack[stack.length] = s[i];
  14.       }
  15.     }
  16.   }
  17.   return stack.join('');
  18. };
  19. /**
  20.  * 时间复杂度：O(n)
  21.  * 空间复杂度：O(n)
  22.  */

四、其他解法