Leetcode 1209. Remove All Adjacent Duplicates in String II

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，使用数据结构栈来解决这个问题，时间复杂度O(N)。字符每次入栈之前都与栈顶元素进行比较，如果不同，则入栈元组，元组元素为当前字符以及字符个数1，如果字符相同且栈顶相同字符个数不等于k-1，也入栈元组，元组元素为当前字符以及连续相同字符个数，值为栈顶字符的个数加1，否则，移除栈顶的k-1个字符。

• Version 1

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        res = []
        for ch in s:
            if not res or res[-1][0] != ch:
                res.append((ch, 1))
            else:
                if res[-1][1] == k -1:
                    del res[-k+1:]
                else:
                    res.append((ch, res[-1][1] + 1))
        res = [x[0] for x in res]
        return ''.join(res)

解析：另一种使用栈的方式，当前字符与栈顶字符相同时，只更新栈顶字符的个数。

• Version 2

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        res = []
        for ch in s:
            if not res or res[-1][0] != ch:
                res.append([ch, 1])
            else:
                if res[-1][1] == k -1:
                    res.pop()
                else:
                    res[-1][1] += 1
        res = [x[0] * x[1] for x in res]
        return ''.join(res)

Reference

1. https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/