Removing Stars From a String
Removing Stars From a String: each * deletes the closest non-star character to its left, along with the star itself. Return the string once every star has been applied.
- 1 <= s.length <= 10⁵
- s consists of lowercase English letters and stars *.
- The operation is always possible.
Intuition
Removing stars from a string processes a string where each * deletes itself and the closest non-star character to its left. Stars are applied left to right, and the result is guaranteed non-empty of stars.
Repeatedly scanning backwards for each star is O(n²). The observation that fixes it is about which character a star removes:
- A star always deletes the most recently surviving character, which is precisely what a stack's top holds.
So walk the string once: push ordinary characters, and on a *, pop instead.
That single rule handles every case, including consecutive stars. In "ab**", the first star pops b and the second pops a, because after the first pop the top has changed. No rescanning is needed — the exposed top is always the correct next victim.
The stack read bottom to top is the answer, already in order, with no reversal required.
The problem guarantees enough characters exist for every star, so no empty-stack check is strictly needed — though adding one costs nothing and protects against malformed input.
A character array or string builder works as well as a formal stack, since only the last element is ever inspected or removed. In Python a list with append and pop is exactly right.
Building the final string with a single join is O(n); concatenating in the loop would be O(n²) in languages with immutable strings.
Each character is pushed and popped at most once, giving O(n) time and O(n) space.
'Closest to the left that still survives' is the stack signature, stated in plain English. Whenever a rule reaches backwards to the most recent unconsumed item, reach for a stack — the same reading solves Backspace String Compare, Remove All Adjacent Duplicates, and Asteroid Collision.
Approach
Before reading on: as you scan left to right, which single character is a star always going to delete? Name the data structure whose top is exactly that character. Aim for one pass.
Identify what a star removes
A star deletes the most recently surviving character, which is exactly the top of a stack. That correspondence is the whole solution.
Push ordinary characters
Walk the string once, pushing every non-star character. The stack holds the survivors in their original order.
Pop on a star
A * removes itself and the top of the stack. One pop per star, with no scanning backwards.
Let consecutive stars cascade
In "ab**", the first star pops b and the second pops a — after each pop the exposed top is already the correct next victim.
Read the stack in order
Bottom to top is the answer, needing no reversal. Join once at the end rather than concatenating in the loop.
Cost of the approach
Each character is pushed and popped at most once, giving O(n) time and O(n) space for the stack.
Solution & live demo
Common pitfalls
Deleting from the string in a loop
while '*' in s:
i = s.index('*')
s = s[:i-1] + s[i+1:]for ch in s:
if ch == '*': stack.pop()
else: stack.append(ch)Every deletion rebuilds the string, so this is O(n²) and times out at 10⁵ characters. The stack achieves the same result in one pass.
Removing the star but not the character
if ch != '*':
stack.append(ch)if ch == '*':
stack.pop()
else:
stack.append(ch)A star deletes two things: itself and the character to its left. Skipping stars without popping leaves every letter in place and returns the input with stars stripped.
Popping the wrong end
stack.pop(0)
stack.pop()
pop(0) removes the first character, not the nearest one to the left of the star. It is also O(n) per call, turning the solution quadratic as well as wrong.
Edge cases
Every character is pushed and nothing pops, so the input is returned unchanged.
Two pops peel off 'b' then 'a', leaving an empty string.
The letter is pushed then popped, giving an empty result.
The stack empties and the answer is the empty string, which is valid.
Each star pops the current top, so deletions interleave correctly with pushes.