Erase Each Star and Its Nearest Remaining Letter to the Left
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Repeatedly choose a star in `s` and remove it together with the closest non-star character to its left. The input guarantees valid removals and a unique final string. Return that string after every star has disappeared.
```cpp
class Solution {
public:
string removeStars(string s);
};
```
### Examples
**Example 1:**
```text
Input: s = "abc*d*"
Output: "ab"
Explanation: The first star removes c, and the second removes d.
```
**Example 2:**
```text
Input: s = "xy**z"
Output: "z"
Explanation: The two stars remove y and x; the final z remains.
```
### Constraints
- `1 <= s.length <= 100000`.
- s contains lowercase English letters and stars*.
- The stated removals can be performed.
### Clarifying Questions
- Which character does a star remove? The nearest remaining non-star character to its left.
- Are removals always possible? Yes, the input guarantees this.
- Can the result be empty? Yes.
- Can the choice of removal order change the required result? No; the final string is guaranteed unique.
```hint Check the boundary
Trace consecutive stars after a run of letters, removing one surviving letter for each star.
```
Overview: Remove each star together with its nearest remaining letter to the left and return the unique surviving string.
