1209. Remove All Adjacent Duplicates in String II

Leetcode #: 1209
Name: Remove All Adjacent Duplicates in String II
Difficulty: Medium
Url: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

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.

Code

Python | Time: O(n) where there will be in-total n insertions and deletions from our Stack | Space: O(n) where n is the # of characters in the given string s

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub