# 1209. Remove All Adjacent Duplicates in String II

--

Leetcode #: 1209
Name: Remove All Adjacent Duplicates in String II
Difficulty: Medium

# Prompt

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

`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"`

Constraints

• `1 <= s.length <= 105`
• `2 <= k <= 104`
• `s` only contains lowercase English letters.

# Approach

Once we’ve detected a character to appear k times in the given string, then we want to simply remove that character. The scenario in which we need to account for is if a group of k duplicate characters emerges subsequent to a removal of k characters from our given string (as depicted by the example above).

We’ll want to iterate through each character in our given string from left to right and keep track of the count of each character in a Stack data structure. Specifically, we’ll want to store a tuple (character, count) in our Stack but alternatively you can just maintain 2 individual Stacks — one for maintaining the characters and the other maintaining its corresponding count. Once we’ve detected that a character appeared k times, we can pop or remove that character from our Stack.

Once we’ve examined each character in our given string and our Stack is still populated with elements, then we want to iterate through each tuple in our Stack and recreate our final result string that we’ll return.