Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.

Example 1:

Input: "abbaca"Output: "ca"Explanation: Forexample, in"abbaca"wecouldremove"bb"sincethelettersareadjacentandequal, andthisistheonlypossiblemove. Theresultofthismoveisthatthestringis"aaca", ofwhichonly"aa"ispossible, sothefinalstringis"ca".

Note:

1. 1 <= S.length <= 20000
2. S consists only of English lowercase letters.

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

用栈模拟，类似“对对碰”，一旦新来的字符和栈顶的字符一样的话，就弹出栈顶字符，直至扫完整个字符串。栈中剩下的字符串就是最终要输出的结果。