本篇推文共計(jì)2000個(gè)字，閱讀時(shí)間約3分鐘。

題目描述：

給出由小寫字母組成的字符串 S，重復(fù)項(xiàng)刪除操作會(huì)選擇兩個(gè)相鄰且相同的字母，并刪除它們。

在S上反復(fù)執(zhí)行重復(fù)項(xiàng)刪除操作，

直到無(wú)法繼續(xù)刪除。

在完成所有重復(fù)項(xiàng)刪除操作后返回最終的字符串。

答案保證唯一。

示例：

輸入："abbaca"
輸出："ca"

解釋：
在 "abbaca" 中，
我們可以刪除 "bb" 由于兩字母相鄰且相同，
這是此時(shí)唯一可以執(zhí)行刪除操作的重復(fù)項(xiàng)。
之后我們得到字符串 "aaca"，
其中又只有 "aa" 可以執(zhí)行重復(fù)項(xiàng)刪除操作，
所以最后的字符串為 "ca"。

提示：

1. 1 <= S.length <= 20000

2. S僅由小寫英文字母組成。

由題目可知，

本題需要注意的要點(diǎn)有兩個(gè)

1.兩個(gè)相鄰且相同字符會(huì)被刪除。

(注意:是需要?jiǎng)h除兩個(gè)相同的字符)

2.刪除字符串中兩個(gè)相鄰并且相同的字符可能會(huì)產(chǎn)生新的相鄰并且相同的字符。

比如題目中的"abbaca"。刪除bb后，會(huì)產(chǎn)生新的字符串a(chǎn)aca,
此時(shí)也需要將aa刪除
最后的字符串為ca

我們根據(jù)要點(diǎn)可知，并不能一次字符串刪除操作就達(dá)到最終目的，我們需要每次刪除完一對(duì)相鄰相同的字符后，再看新的字符串是否存在相鄰相同的一對(duì)字符。

根據(jù)分析我們可以用一個(gè)數(shù)據(jù)結(jié)構(gòu)，也就是棧，存儲(chǔ)每次比較的結(jié)果。

同時(shí)可以從左到右的遍歷一次字符串S的所有字符Si，和棧中的棧頂元素比較。

如果Si與棧頂元素相同，

則說(shuō)明兩個(gè)字符相鄰且相同，或者是由于中間元素被刪除后導(dǎo)致的間接相鄰相同。

如果Si與棧頂元素不相同，

則說(shuō)明兩個(gè)字符無(wú)法被消除，滿足題目條件，則把此時(shí)的字符Si入棧。

我們用字符串a(chǎn)bbaca，和一個(gè)初始為空的棧描述一下代碼處理過(guò)程。

初始情況，棧內(nèi)為空，

字符串S指向第一個(gè)字符S0=a

由于棧為空，將S0=a入棧

字符串指針指向S1=b

此時(shí)對(duì)S1=b與棧頂元素a作出判斷，

二者不相同，S1=b入棧

字符串指針指向S2=b

此時(shí)對(duì)S2=b,與棧頂元素b作出判斷，

二者相同，S2=b與棧頂元素b消除

字符串指針指向S3=a

此時(shí)對(duì)S3=a與棧頂元素a作出判斷，二者相同，S3=a與棧頂元素a消除

字符串指針指向S4=c

由于棧為空，將S4=c入棧

字符串指針指向S5=a

此時(shí)對(duì)S5=a與棧頂元素c作出判斷，

二者不相同，S5=a入棧

我們用代碼表示如下：

class Solution:
    def removeDuplicates(self, S: str) -> str:
        stk = list()
        for ch in S:
            if stk and stk[-1] == ch:
                stk.pop()
            else:
                stk.append(ch)
        return "".join(stk)