0350MediumStringStack

Token Tape Compactor

Tracked in this browser only

Trains the technique from

LeetCode 1209Remove All Adjacent Duplicates in String II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def remove_duplicates(s: str, k: int) -> str:

Java

public String removeDuplicates(String s, int k)

The intended approach

Time O(n)Space O(n)

Sweep the tape once with a stack whose entries pair a letter with the length of the run of that letter ending at the current position. A token extends the top run when the letters agree, otherwise it opens a new run. As soon as a run reaches `k` its entry is popped, which leaves the runs that surrounded it adjacent, so the next token naturally continues the run underneath. Rebuild the tape from the runs that survive.

Pythonentry point: remove_duplicates

def remove_duplicates(s, k):
    # Carry a stack of [letter, run length].  Each letter either extends the run on
    # top or opens a new one, and a run that reaches k is popped off, which puts the
    # runs on either side of it next to each other so they can merge on the spot.
    # Time O(n).  Space O(n) for the stack and the rebuilt tape.
    stack = []
    for ch in s:
        if stack and stack[-1][0] == ch:
            stack[-1][1] += 1
            if stack[-1][1] == k:
                stack.pop()
        else:
            stack.append([ch, 1])
    pieces = []
    for ch, run in stack:
        pieces.append(ch * run)
    return "".join(pieces)

The obvious version

Scan the tape for the first run of at least `k` matching tokens, cut `k` tokens out of it by rebuilding the string, and start over. Repeats until a full scan finds no such run.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_compact_tape(s, k):
    tape = s
    while True:
        cut_at = -1
        i = 0
        n = len(tape)
        while i < n:
            j = i
            while j < n and tape[j] == tape[i]:
                j += 1
            if j - i >= k:
                cut_at = i
                break
            i = j
        if cut_at < 0:
            return tape
        tape = tape[:cut_at] + tape[cut_at + k:]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in