Removing Stars From a String
Medium · Stack & Strings · String · Stack · Simulation
Problem
You get a string s of lowercase letters and stars *. A star works like a backspace: it deletes itself and the closest letter to its left that is still there.
Apply every star and return the string that is left. The input is built so that each star always has a letter to delete, and the result does not depend on the order the stars are applied in.
Examples
Input: s = "leet**cod*e" Output: "lecoe"
The two stars after leet delete t and then e; the star after cod deletes d.
Input: s = "erase*****" Output: ""
Five stars, five letters: nothing survives.
Input: s = "ab*c" Output: "ac"
The only star deletes b, the letter right before it.
Constraints
- 1 <= s.length <= 10^5
- s holds lowercase English letters and *
- every star has a letter to its left to delete
Approaches
- Apply stars one at a time — time O(n²), space O(n)
Follow-up
The same stack solves backspace editors, bracket matching and "remove adjacent duplicates". What changes if a star may appear when no letter is left (it would do nothing), or if each star deletes the closest letter to its right instead?
Related problems
Start free on Cariara · Coding problems · System design studio
