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
'Closest surviving character to the left' is precisely the top of a stack. Push letters as they arrive; when a star appears, pop. The stack always holds exactly the characters that have survived so far, so no rescanning is ever needed.
'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.
The deletion target is always the most recent survivor
A star removes the nearest non-star character to its left that has not already been removed. As you scan left to right, that character is by definition the last one you kept — the stack top. This is the whole insight: the problem's wording describes stack behaviour without naming it, and once you see that, the implementation is three lines.
Push letters, pop on stars
For each character: if it is a star, pop the stack; otherwise push it. Because the problem guarantees every star has a character to delete, the stack is never empty when a pop occurs — though a defensive if stack guard costs nothing. Consecutive stars naturally peel off successive survivors, and a star immediately after a deletion targets whatever is newly exposed.
The stack is the answer
When the scan ends, the stack holds the survivors in their original order, so joining it bottom-to-top gives the result directly. Each character is pushed at most once and popped at most once, giving O(n) time. Space is O(n) for the stack, which is also the output, so nothing is truly wasted. A naive repeated-deletion approach would be O(n²) because each removal shifts the tail.
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.