Lexicographically Minimum String After Removing Stars
01 · Problem
You are given a string s consisting of lowercase English letters and '*' characters.
Process the stars from left to right. For the leftmost remaining '*', delete it together with the smallest letter to its left that has not been deleted yet. If that smallest letter appears several times to the left of the star, delete the rightmost of those occurrences (this choice keeps the final string lexicographically smallest). Repeat until no stars remain.
Return the resulting string. It is guaranteed that every '*' has at least one undeleted letter to its left when it is processed, so the operation is always possible. The result may be the empty string "".
02 · Examples
s = "aaba*"
"aab"
The smallest letter left of the star is 'a', occurring at indices 0, 1 and 3. Remove the rightmost one (index 3) together with the star, leaving "aab".
s = "abc"
"abc"
There are no stars, so the string is unchanged.
s = "de*c*"
"e"
The first star removes 'd' (smallest of "de"), leaving "ec*". The second star removes 'c', leaving "e".
03 · Constraints
- 011 <= s.length <= 105
- 02s consists only of lowercase English letters and '*'
- 03Every '*' can be paired with an undeleted letter to its left (the input is always valid)
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.