---
# System prepended metadata

title: 1209. Remove All Adjacent Duplicates in String II
tags: [Leetcode, Bloomberg, Medium, Stack]

---

# 1209. Remove All Adjacent Duplicates in String II
###### tags: `Leetcode` `Medium` `Bloomberg` `Stack`
Link: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/
## 思路 $O(N)$ $O(N)$
用stack做
但是不同于之前有重复的就消除的那题，这次因为是要一次删除多个，用stack存每个字符，每次检查的时候把一样的全都pop出来，再push回去，就会很浪费时间，所以选择动态更新string的方法
## Code
```python=
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        for c in s:
            if stack and stack[-1][0] == c:
                stack[-1][1] += 1
                if stack[-1][1] == k:
                    stack.pop()
            else:
                stack.append([c, 1])
        return ''.join(c*k for c,k in stack)
```
```java=
class Solution {
    public String removeDuplicates(String s, int k) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> counts = new Stack<>();
        for(int i = 0;i < sb.length();i++){
            if(i==0 || sb.charAt(i)!=sb.charAt(i-1)){
                counts.push(1);
            }
            else{
                int count = counts.pop();
                count += 1;
                if(count == k){
                    sb.delete(i-k+1,i+1);
                    i = i-k;
                }
                else{
                    counts.push(count);
                }
            }
        }
        return sb.toString();
    }
}
```