3170. Lexicographically Minimum String After Removing Stars

Problem Link

Description

---

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.

While there is a '*', do the following operation:

• Delete the leftmost '*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.

Return the lexicographically smallest resulting string after removing all '*' characters.

 

Example 1:

Input: s = "aaba*"

Output: "aab"

Explanation:

We should delete one of the 'a' characters with '*'. If we choose s[3], s becomes the lexicographically smallest.

Example 2:

Input: s = "abc"

Output: "abc"

Explanation:

There is no '*' in the string.

 

Constraints:

• 1 <= s.length <= 105
• s consists only of lowercase English letters and '*'.
• The input is generated such that it is possible to delete all '*' characters.

Solution

---

Python3

class Solution:
    def clearStars(self, s: str) -> str:
        N = len(s)
        mp = [[] for _ in range(26)]
        stack = []
        deleted = [False] * N
        
        for i, x in enumerate(s):
            if x == "*":
                deleted[i] = True
                
                for k in range(26):
                    if len(mp[k]) > 0:
                        j = mp[k].pop()
                        deleted[j] = True
                        break
            else:
                mp[ord(x) - ord('a')].append(i)
        
        return "".join(s[i] for i in range(N) if not deleted[i])