839. Squashing Runs of k Equal Letters

You are given a lowercase string s and an integer k.

Repeatedly pick any k ADJACENT equal letters and delete them, closing the gap so that the two sides become neighbours. Keep going until no k adjacent letters are equal, and print what is left. Print the word empty if nothing remains.

deeedbbcccbdaa, k = 3 -> aa aaa, k = 2 -> a abcd, k = 2 -> abcd

Trace the first one. eee goes, leaving ddbbcccbdaa. Then ccc goes, leaving ddbbbdaa. Now bbb has appeared where the cc used to separate it, so that goes too, leaving dddaa, then ddd goes, and aa remains.

The order of deletions never changes the final string. Deleting a run somewhere else first can only ever merge the same letters, never different ones.

## Why deleting repeatedly is too slow

Doing exactly what the statement says means rescanning after every deletion. On aaaa...a with k = 2 that is n/2 deletions, each after a scan of what is left, so roughly n^2 / 4 character comparisons. At n = 200000 that is 10^10.

## The stack that carries counts

Walk the string once with a stack of pairs (letter, run length).

if the stack is non-empty and its top letter equals c: add one to the top count if the count reaches k, pop the pair entirely otherwise: push (c, 1)

The stack always describes the string built so far AFTER all possible deletions, compressed into runs. When a pair is popped, the pair below it becomes the new top, which is exactly the merge that the slow simulation has to rescan for. It is handled by doing nothing.

## Why one pass is enough

A deletion can only make the two neighbours of the deleted run adjacent, and the left neighbour is already directly below on the stack. Nothing further left can be affected, because the letters between are unchanged. So the merge cascade always travels DOWN the stack and never back across material already passed.

This is the same "popped means finished" argument as the numeric problems, applied to letters: a completed run is either merged into the one below it or is final.

## What is left at the end

The stack, bottom to top, spells the answer: each pair contributes its letter repeated count times. It cannot be printed top down, and it cannot be printed as letters without their counts.

## The two traps

A run of length k must be popped the moment the count REACHES k, not once it passes it; testing > k lets runs grow past the limit and aaaa with k = 2 wrongly survives.

And the answer can be empty, which is why there is a word to print for it.

## Related problems

Problem 165 removes adjacent PAIRS, which is this with k fixed at 2 and no counts needed. Carrying the count is the whole step up.

## Cost

Time O(n): each character is pushed once, and each pop removes a whole run. Space O(n).

Constraints - `1 ≤ |s| ≤ 200000` - `2 ≤ k ≤ 200000` - `s` contains lowercase letters only