Lexicographically Minimum String After Removing Stars

You are tasked with transforming a given string by removing characters that are marked with an asterisk. The goal is to achieve the lexicographically smallest possible string after these removals. This is a common problem in string manipulation and optimization, where efficiency and correct ordering are paramount.

Problem Description

Given a string s that may contain lowercase English letters and asterisks ('*'), you need to process the string and remove characters based on the following rules:

1. An asterisk '*' acts as a backspace character.
2. When an asterisk is encountered, it removes the immediately preceding non-asterisk character.
3. If an asterisk is encountered and there is no preceding non-asterisk character, the asterisk is removed itself.
4. After processing all characters and removals, the remaining characters form the final string.

Your objective is to return the lexicographically smallest possible string among all valid outcomes. If multiple characters could be removed by an asterisk, you should prioritize removing the one that leads to the lexicographically smallest final string.

Key Requirements:

• Process the string from left to right.
• Handle cases where asterisks appear at the beginning or consecutively.
• Ensure the final string is the lexicographically smallest.

Expected Behavior:

The function should return a string.

Edge Cases to Consider:

• An empty input string.
• A string containing only asterisks.
• A string containing only non-asterisk characters.
• Asterisks appearing at the beginning of the string.
• Multiple consecutive asterisks.
• The removal process leading to an empty string.

Examples

Example 1:

Input: s = "leet*code*"
Output: "lecd"
Explanation:
1. 'l' is added. Current: "l"
2. 'e' is added. Current: "le"
3. 'e' is added. Current: "lee"
4. 't' is added. Current: "leet"
5. '*' encountered. It removes the preceding 't'. Current: "lee"
6. 'c' is added. Current: "leec"
7. 'o' is added. Current: "leeco"
8. 'd' is added. Current: "leecod"
9. 'e' is added. Current: "leecode"
10. '*' encountered. It removes the preceding 'e'. Current: "leecod"
The final string is "leecod".

Example 2:

Input: s = "a*b*c"
Output: ""
Explanation:
1. 'a' is added. Current: "a"
2. '*' encountered. It removes 'a'. Current: ""
3. 'b' is added. Current: "b"
4. '*' encountered. It removes 'b'. Current: ""
5. 'c' is added. Current: "c"
The final string is "c".
Wait, this explanation is incorrect for the "lexicographically smallest" requirement. Let's re-evaluate Example 2 with the true requirement.

**Example 2 (Corrected):**

Input: s = "abc" Output: "c" Explanation:

1. Process 'a': The temporary result is 'a'.
2. Process '*': It must remove the preceding non-asterisk character. The only candidate is 'a'. The temporary result becomes empty.
3. Process 'b': The temporary result is 'b'.
4. Process '*': It must remove the preceding non-asterisk character. The only candidate is 'b'. The temporary result becomes empty.
5. Process 'c': The temporary result is 'c'. The final string is "c".

**Example 3:**

Input: s = "abcde" Output: "abcd" Explanation:

1. 'a' -> "a"
2. 'b' -> "ab"
3. 'c' -> "abc"
4. '*' -> removes 'c'. Current: "ab"
5. 'd' -> "abd"
6. 'e' -> "abde"
7. '*' -> removes 'e'. Current: "abd" The final string is "abd".

**Example 4:**

Input: s = "**abc" Output: "abc" Explanation:

1. '' encountered. No preceding non-asterisk char. '' is removed. Current: ""
2. '' encountered. No preceding non-asterisk char. '' is removed. Current: ""
3. 'a' -> "a"
4. 'b' -> "ab"
5. 'c' -> "abc" The final string is "abc".

**Example 5:**

Input: s = "abc*" Output: "" Explanation:

1. 'a' -> "a"
2. '*' -> removes 'a'. Current: ""
3. 'b' -> "b"
4. '*' -> removes 'b'. Current: ""
5. 'c' -> "c"
6. '*' -> removes 'c'. Current: "" The final string is "".

## Constraints

*   `1 <= s.length <= 10^5`
*   `s` consists of lowercase English letters and '*'.
*   The processing and generation of the final string should be efficient.

## Notes

Consider using a data structure that allows for efficient addition and removal of elements from the "end" of a sequence. The lexicographical ordering implies that when you have a choice of which character to remove (which shouldn't happen with the current rule of removing the *immediately preceding* non-asterisk character, but it's good to keep in mind for similar problems), you'd choose the one that results in a smaller string. In this specific problem, the rule is deterministic. Think about how to maintain the state of the string as you iterate through it.