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 <= 105
2 <= k <= 104
s only contains lower case English letters.
- code
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = []
res = list(s)
quick = slow = 0
while quick < len(s):
res[slow] = res[quick]
if (slow == 0 or res[slow] != res[slow - 1]):
stack.append(1)
else:
inc = stack.pop() + 1
if inc == k:
slow -= k
else:
stack.append(inc)
quick += 1
slow += 1
return "".join(res[:slow])