Removing Stars From a String
The key idea
Each star deletes the closest surviving character to its left. That is exactly last-in, first-out behavior: build a stack of letters, and on every star pop the top. Whatever remains on the stack, read bottom-to-top, is the answer.
Problem
You are given a string s containing lowercase English letters and * characters. In one operation, you choose a * in s, then remove the closest non-star character to its left, as well as the * itself.
Return s after all stars have been removed.
Note: The input will be generated such that the operation is always possible, and the answer will be unique.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters and stars
* - The operation above can be performed on s.
Examples
Input: s = "leet**cod*e"
Output: "lecoe"
Input: s = "erase*****"
Output: ""
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization