Problem Statement in English

You’re given a string s consisting of lowercase English letters and stars (*). Each star represents a character that can be removed from the string. The goal is to remove the stars in such a way that the resulting string is lexicographically minimum.

Approach

To solve the problem, we can use a min-heap to keep track of the characters in the string. As we iterate through the string, we will push characters onto the heap and pop them when we encounter a star.

The result will be built by popping characters from the heap while ensuring that we do not include any stars.

Solution in Python


class Solution:
    def clearStars(self, s: str) -> str:
        minheap = []

        removed = set()

        for i, char in enumerate(s):
            if char == "*":
                c, i = heappop(minheap)
                removed.add(-i)
            else:
                heappush(minheap, (char, -i))

        res = ""

        for i, char in enumerate(s):
            if i not in removed and char != "*":
                res += char

        return res

Complexity

  • Time: $O(nlogn)$
    Since we pop from the heap.

  • Space: $O(n)$
    Since we store the characters in a heap and a set.

And we are done.