Remove All Adjacent Duplicates in String II
Medium · stack
You are given a string s of lower-case letters and an integer k.
A deletion picks k equal letters that sit next to each other and removes all of them. The letters on either side of the gap then become neighbours, so a new run of k equal letters may appear.
Keep deleting until there is no run of k equal neighbours left, and return the string that remains (the empty string if everything is deleted). The final string is the same whichever run you delete first.
Examples
Example 1
Input: s = "pbbbcccpp", k = 3
Output: ""
Deleting bbb and then ccc leaves ppp, and deleting that leaves nothing.
Example 2
Input: s = "aabbbbac", k = 4
Output: "aaac"
Only bbbb is a run of four, and deleting it leaves aaac.
Example 3
Input: s = "abcd", k = 2
Output: "abcd"
No two equal letters are neighbours, so nothing happens.
Constraints
- 1 <= len(s) <= 3000
- 2 <= k <= 3000
- s contains only lower-case English letters