667. Removing Stars From a String
You are given a string s made of lowercase letters and * characters. Each star is a tiny eraser: it deletes the closest letter to its left that has not already been deleted, and then disappears itself.
Apply every star and return the string that remains.
The input is guaranteed to be well-formed — whenever a star fires, there is always a surviving letter to its left — and the final string is guaranteed to be non-empty. It can be shown the result is the same no matter what order the stars are applied in.
Example 1:
Input: s = "pla*net*s"
Output: "plnes"
Explanation: The first star erases the 'a' just before it, leaving "pl" + "net*s". The second star erases the 't'. What survives, in order, is p, l, n, e, s.
Example 2:
Input: s = "ab*c**d"
Output: "d"
Explanation: The first star erases 'b'. Then 'c' arrives, and the next star erases it; the star after that erases 'a'. Everything is gone until 'd' arrives — so only "d" remains.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists of lowercase English letters and '*' characters.
- Every star has a surviving letter to its left when it fires, and the final string is non-empty.
Hints:
Literally re-doing the deletions on the string — find a star, splice out two characters, repeat — is O(n) per star and O(n²) overall. The stars near the end of a long string make this crawl.
Read s left to right and ask: when a star arrives, which letter is "the closest surviving letter to its left"? It is always the most recently kept one — last in, first out.
That is a stack. Push letters; on '*', pop once. The stack's contents, bottom to top, are the answer.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "pla*net*s"
Expected output: "plnes"