LeetCode 1209 Remove All Adjacent Duplicates in String II

LeetCode

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example 1:

Input: s = “abcd”, k = 2
Output: “abcd”
Explanation: There’s nothing to delete.

Example 2:

Input: s = “deeedbbcccbdaa”, k = 3
Output: “aa”
Explanation: First delete “eee” and “ccc”, get “ddbbbdaa”
Then delete “bbb”, get “dddaa”
Finally delete “ddd”, get “aa”

Example 3:

Input: s = “pbbcggttciiippooaais”, k = 2
Output: “ps”

Constraints:

1 <= s.length <= 10<sup>5</sup> 2 <= k <= 10<sup>4</sup>
* s only contains lower case English letters.

题目大意：

字符串中去除连续k次的字符

解题思路：

一开始用暴力法得到LTE。这题由于需要保持顺序，且元素之间是相等关系且类似于LeetCode 316 Remove Duplicate Letters，考虑用Stack。

解题步骤：

N/A

注意事项：

1. Stack中存元素和该元素的连续个数，这样避免往前重新计算连续了几次。若栈顶元素等于遍历元素且栈顶连续个数为k - 1就连续出栈。此情况此遍历元素不入栈

Python代码：

def removeDuplicates(self, s: str, k: int) -> str:
	stack, res = [], ''
	for i in range(len(s)):
		if stack and stack[-1][0] == s[i] and stack[-1][1] == k - 1:
			while stack and stack[-1][0] == s[i]:
				stack.pop()
		else:
			if stack and stack[-1][0] == s[i]:
				stack.append((s[i], stack[-1][1] + 1))
			else:
				stack.append((s[i], 1))
	while stack:
		pair = stack.pop()
		res += pair[0]
	return res[::-1]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)