DSA problem
Removing Stars From a String
You are given a string s, which contains stars *. In one operation, you can choose a star in s, remove the closest non-star character to its left, as well as remove the star itself. Return the string after all stars have been removed.
The operations can be performed in any order, but the problem guarantees that the operation is always possible (every star has at least one non-star character to its left at the time it is processed). It also guarantees that the resulting string will not be empty when read left to right — though the output can certainly become empty if every character pairs up.
A naive simulation removes one star at a time, each time scanning leftward to find the closest non-star character. This can be O(n^2) in pathological inputs.
The clean solution observes that "remove the most recent non-star" is exactly what a stack does in O(1). Walk s left to right with a stack: for each character, if it is a star, pop the stack (which removes the most recent non-star character); otherwise, push the character. After the pass, the stack (bottom to top) is the answer. This is O(n) time and O(n) space.
Examples
s = "leet**cod*e""lecoe"s = "erase*****"""s = "abc***"""Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters and stars *.
- The operation above can be performed on s.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.