Problem of The Day: Lexicographically Minimum String After Removing Stars

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def clearStars(self, s: str) -> str:
        arr = [0] * 26
        next_smallest = 0

        queue = deque(list(s))
        res = deque()
        while queue:
            c = queue.popleft()
            if c == '*':
                for i in range(26):
                    if arr[i] > 0:
                        next_smallest = i
                        break

                next_pop_char = chr(next_smallest + ord('a'))
                arr[next_smallest] -= 1
                stack = []
                while res:
                    cc = res.pop()
                    if cc == next_pop_char:
                        break
                    stack.append(cc)
                while stack:
                    res.append(stack.pop())
            else:
                i = ord(c) - ord('a')
                arr[i] += 1
                res.append(c)

        return ''.join(res)

Editorial

Approach: Greedy

class Solution:
    def clearStars(self, s: str) -> str:
        cnt = [[] for _ in range(26)]
        arr = list(s)
        for i, c in enumerate(arr):
            if c != "*":
                cnt[ord(c) - ord("a")].append(i)
            else:
                for j in range(26):
                    if cnt[j]:
                        arr[cnt[j].pop()] = "*"
                        break
        return "".join(c for c in arr if c != "*")