Remove every '*' and also delete one earlier character for each star so the final string is lexicographically smallest.
You are given a string s consisting of lowercase English letters and the character '*'.
Process the string from left to right. Each time you encounter a '*', you must remove that star and also remove exactly one previously seen lowercase letter. The removed letter can be any letter that appears before the star and has not already been removed.
Your goal is to choose removals so that, after all stars are processed and deleted, the resulting string is lexicographically minimum among all valid outcomes.
Return the final string.
A string a is lexicographically smaller than string b if at the first position where they differ, a has a smaller character, or if one string is a prefix of the other and is shorter.
Input Format
- A single string
s. scontains lowercase English letters and'*'characters.
Output Format
- Return the lexicographically smallest possible string after removing all stars and one earlier letter for each star.
Constraints
1 <= s.length <= $10^{5}$scontains only lowercase English letters and'*'- It is guaranteed that at every
'*', there is at least one earlier non-removed letter available to delete.
Example 1
Input
s = "aaba*"
Output
"aab"
Explanation
When the star appears, deleting the last a gives the smallest result among valid choices. The final string is "aab".
Example 2
Input
s = "abc*d*"
Output
"ab"
Explanation
For the first star, delete c. For the second star, delete d. Removing all stars leaves "ab".
Show 1 more example
Example 3
Input
s = "cb*a*"
Output
"a"
Explanation
Delete b for the first star, then delete c for the second star. The remaining string is "a".
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.