Removing Stars From a String

Start dumb: find and cut, over and over

The literal reading of the rule: scan for a *, delete it together with the nearest non-star character to its left, and repeat from scratch until no stars remain. It works, but every deletion rescans and rebuilds the string — O(n²) in the worst case (abcd****), all of it re-discovering where the “nearest surviving letter to the left” is.

Find the bottleneck

That phrase — nearest surviving letter to the left — is the whole problem. Each rescan walks left looking for a character the previous scans already walked past. The letter a star cancels is always the most recently kept one, and the algorithm keeps forgetting it.

The optimal shape

One pass, one stack (a StringBuilder works as one):

1. Letter → push it; nothing can cancel it yet, so it waits on top.
2. * → pop the top; the star and that letter annihilate together.
3. After the scan, whatever is left on the stack — read bottom to top — is the answer.

Each character is touched a constant number of times, so it’s O(n) time and O(n) space. In the player, surviving letters stay highlighted as the stack “window”; a star and its victim both retire to a dashed conflict tile.

Watch it think

Run the default, then the traps: erase***** (every letter cancelled — the result is empty), ab*c (a single deletion in the middle), and a lone letter like x (no star ever fires, so it sails straight through).

1fun removeStars(s: String): String {
2    val stack = StringBuilder()
3    for (c in s) {
4        if (c == '*') {
5            stack.deleteCharAt(stack.length - 1)
6        } else {
7            stack.append(c)
8        }
9    }
10    return stack.toString()
11}