Show problems as
Classic problem #1209MediumStringStack

Remove All Adjacent Duplicates in String II

Real-world version: Token Tape Compactor
Tracked in this browser only
Read Remove All Adjacent Duplicates in String II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tape of tokens is written as the lowercase string s. A compactor works on it one step at a time.

A step picks any spot where k neighbouring tokens all carry the same letter, lifts exactly those k tokens off the tape, and lets the two loose ends join, which may put fresh neighbours side by side. Steps keep going while some spot still has k matching neighbours.

Whichever spots the compactor picks, the tape it finishes with is the same, so return that final tape as a string. It may be empty.

Examples

Example 1

Input
s = "abbbaaac", k = 3
Output
"ac"

Lifting the three `b` tokens joins the leading `a` to the three that followed them, giving `aaaac`. Three of those four `a` tokens then come off, leaving `ac`, which has no spot with three matching neighbours.

Example 2

Input
s = "aaaa", k = 3
Output
"a"

One step removes three of the four `a` tokens. A single `a` is left and no further step applies.

Example 3

Input
s = "ppqqppqq", k = 2
Output
""

Removing the leading `pp` leaves `qqppqq`; removing that `qq` leaves `ppqq`, then `qq`, then nothing at all.

Constraints

  • 1 <= s.length <= 10^5
  • 2 <= k <= 10^4
  • s holds lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def remove_duplicates(s: str, k: int) -> str:
Java
public String removeDuplicates(String s, int k)

More on the same topics