Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each star must remove the smallest available letter to its left. When that letter appears several times, remove its rightmost occurrence: keeping an equal small letter earlier makes the surviving string lexicographically no larger. A stack of positions for each letter supports this tie-breaking rule.

Approach

Scan left to right. For a letter, push its index onto that letter's stack and update the smallest available letter. For a star, mark the star for removal and pop the last index from the smallest letter's stack, marking that position too. If its stack becomes empty, advance the minimum-letter pointer until another nonempty stack is found or the alphabet's end is reached. Later incoming letters can lower the pointer again.

Finally, scan the original string and append every unmarked character in order. The promised feasibility ensures a removable letter exists for each star. Storing indices preserves the relative order of all characters that remain.

class Solution:
    def clearStars(self, s: str) -> str:
        n = len(s)
        map = defaultdict(list)
        avoid = set()
        mn = s[0]

        for i in range(n):
            if s[i] != '*':
                map[s[i]].append(i)
                if s[i] < mn: mn = s[i]
            else:
                avoid.add(i)
                avoid.add(map[mn].pop())
                while mn != 'z' and len(map[mn]) == 0: mn = chr(ord(mn) + 1)
        
        res = []

        for i in range(n):
            if not i in avoid: res.append(s[i])

        return "".join(res)

Complexity analysis

Let n = s.length and sigma = 26. The stack/removal scan takes O(n*sigma) = O(n) time with expected hash-table access. Python constructs a list and joins it, so its total time is O(n). JavaScript repeatedly appends to an immutable string; copying-based concatenation gives a conservative O(n^2) total bound, although engines can optimize it using ropes or other representations. Auxiliary space is O(n) in both versions for the index stacks, removal markers and output construction.