[[419471]]

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

在 S 上反復(fù)執(zhí)行重復(fù)項刪除操作，直到無法繼續(xù)刪除。

在完成所有重復(fù)項刪除操作后返回最終的字符串。答案保證唯一。

示例：

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

提示：

1. <= S.length <= 20000
2. S 僅由小寫英文字母組成。

解法：利用棧

解題思路： 遍歷字符串，依次入棧，入棧時判斷與棧頭元素是否一致，如果一致，即這兩個元素相同相鄰，則需要將棧頭元素出棧，并且當(dāng)前元素也無需入棧

解題步驟： 遍歷字符串，取出棧頭字符，判斷當(dāng)前字符與棧頭字符是否一致

• 不一致，棧頭字符進(jìn)棧，當(dāng)前字符進(jìn)棧
• 一致，即棧頭字符與當(dāng)前字符相同相鄰，都不需要進(jìn)棧，直接進(jìn)入下次遍歷即可

遍歷完成后，返回棧中字符串

代碼實現(xiàn)：

const removeDuplicates = function(S) { 
    let stack = [] 
    for(c of S) { 
        let prev = stack.pop() 
        if(prev !== c) { 
            stack.push(prev) 
            stack.push(c) 
        } 
    } 
    return stack.join('') 
}; 

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n