# 1209. Remove All Adjacent Duplicates in String II

{% embed url="<https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/>" %}

### 12/29/2020 Update:

传说中的一维消糖果，其实用stack最简单快捷，之前想复杂了...

##

本想简单把 Q1047 的解改一改变成双指针，但是TLE了。

{% content-ref url="1047.-remove-all-adjacent-duplicates-in-string" %}
[1047.-remove-all-adjacent-duplicates-in-string](https://xuqiangwen1994.gitbook.io/practice/1047.-remove-all-adjacent-duplicates-in-string)
{% endcontent-ref %}

每次执行删除操作之前，当前位置累计的重复字符数量`memo[i]`只取决于前一位置的重复字符数量`memo[i-1]`和当前字符是否于前字符相同`s[i]==s[i-1]`，所以可以近似看作一个`bottom-up DP`，只不过`i`不是一直向右移动，而是会在每次删除操作之后左移。

{% tabs %}
{% tab title="Stack" %}

```python
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        # we need to track the newly added ch and manipulate it -> stack
        stack = []
        # not only ch, but also it's continously duplicate amount
        # stack [(ch, n)]
        # once the n reaches k, we pop the tailed chs
        for ch in s:
            if stack and ch == stack[-1][0]:
                if stack[-1][1] + 1 == k:
                    stack.pop()
                else:
                    stack[-1][1] += 1
            else:
                stack.append([ch, 1])
        
        return "".join([x[1]*x[0] for x in stack])
```

{% endtab %}

{% tab title="Two Pointers (TLE)" %}

```python
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        i, j = 0, 1
        while s and i < len(s)-k+1:
            if j - i == k:
                s = s[:i]+s[j:]
                i = i-k if i>=k else 0
                j = i + 1
            elif s[j] == s[i]:
                j += 1
            else:
                i += 1
                j = i + 1
        return s
```

{% endtab %}

{% tab title="Pseudo DP" %}

```python
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        n = len(s)
        memo = [0 for _ in range(n)]
        memo[0] = 1
        i = 1
        while 0 <= i < len(s):
            if s[i] == s[i-1]:
                memo[i] = memo[i-1] + 1
                if memo[i] == k:
                    s = s[:i-k+1]+s[i+1:]
                    i = i - k
                    #print(s, i)
            else:
                memo[i] = 1
            i += 1
        return s
    
                
```

{% endtab %}
{% endtabs %}
