Remove Adjacent Groups
MediumStack · SalesForce
You are given a string s and an integer k. A removal deletes k adjacent, equal characters from the string; the parts on either side then join together, which may create a new group to remove.
Keep performing removals until no k adjacent equal characters remain, and return the final string. The final string is the same no matter which group you remove first.
A run longer than k loses exactly k characters per removal; for example with k = 3, "aaaa" becomes "a".
Example 1
- Input:
- s = "xyyyxxzzzw", k = 3
- Output:
- "w"
- Explanation
- Removing
yyyjoins thexwithxxto formxxx, which is removed too. Thenzzzgoes, leavingw.
Example 2
- Input:
- s = "abccbx", k = 2
- Output:
- "ax"
- Explanation
- Removing
ccmakes the twobs adjacent, givingabbx; removingbbleavesax.
Example 3
- Input:
- s = "baaaab", k = 3
- Output:
- "bab"
- Explanation
- The run of four
as loses three, leaving oneabetween thebs, and nothing else can be removed.
Constraints
- 0 ≤
s.length≤ 105 - 2 ≤
k≤ 104 sconsists of lowercase English letters and digits