1209. Remove All Adjacent Duplicates in String II

-
Given a string s, 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^5
  • 2 <= k <= 10^4
  • s only contains lower case English letters.
---
Intuition
We need to traverse the whole string
Look at the current element of the string
If its different than previous, continue
If its same as previous it is potentially a candidate for removal.. keep counting till we reach k
Once we reach k, remove k elements

Data structure which allows us to fetch the latest element just processed is appropriate
Stack seems right
We need to maintain the number of consecutive elements if they are the same
Modify stack to store character, count and check against k
-----
Time - O(n)
Space - O(n)
---
Related problems