---
# System prepended metadata

title: 1047. Remove All Adjacent Duplicates In String
tags: [string, Leetcode, stack, python, c++, easy]

---

###### tags: `Leetcode` `easy` `string` `stack` `python` `c++`

# 1047. Remove All Adjacent Duplicates In String

## [題目連結:] https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/description/

## 題目:
You are given a string ```s``` consisting of lowercase English 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 can be proven that the answer is **unique**.

**Example 1:**
```
Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
```
**Example 2:**
```
Input: s = "azxxzy"
Output: "ay"
```

## 解題想法:
* 此題為，給一string，刪除連續相同的char，重複遍歷直到沒有連續重複char
* 線性遍歷即可:
    * python: 用stack( list )
    * c++: 用string
    * 對於stack每次判斷:
        * 若stack非空 且 新進的char==stack[-1]:
            * stack.pop()
        * 否則:
            * stack.append(當前char)

## Python:
``` python=
class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        res=[]
        for char in s:
            if res and char==res[-1]:
                res.pop()
            else:
                res.append(char)
        return "".join(res)
```

## C++:
``` cpp=
class Solution {
public:
    string removeDuplicates(string s) {
        string res;
        for (auto item: s){
            if (!res.empty() && item==res.back())
                res.pop_back();
            else
                res.push_back(item);
        }
        return res;
    }
};
```