Coding Interview PatternsRemoving Stars From a String
MediumStacks
Removing Stars From a String
Explanation & Solution
Description
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.
Note:
- The input will be generated such that the operation is always possible.
- It can be shown that the resulting string will always be unique.
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e".
sbecomes "lee*cod*e". - The closest character to the 2nd star is 'e' in "lee*cod*e".
sbecomes "lcod*e". - The closest character to the 3rd star is 'd' in "lcod*e".
sbecomes "lcoe".
There are no more stars, so we return "lcoe".
Constraints
1 <= s.length <= 10^5sconsists of lowercase English letters and stars*- The operation above can be performed on
s
Approach
Stacks pattern
1. Stack as Character Buffer
- Use a stack to accumulate non-star characters
2. Process Each Character
- If the character is not a star: push it onto the stack
- If the character is a star: pop the top of the stack (removes the closest non-star character to its left)
3. Build Result
- After processing all characters, the stack contains the remaining characters in order
- Join them to form the result string
Key Insight
- The stack perfectly models the "remove closest left non-star" operation — the most recently added character is always on top
- This is one of the simplest stack problems, but it demonstrates the core stack principle of LIFO deletion
- Time: O(n), Space: O(n)
Visualization
Input:
[l, e, e, t, *, *, c, o, d, *, e]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
12 steps